#223189 (Java21) No.619 CardShuffle

提出ソース

結果

問題	No.619 CardShuffle
ユーザー	37zigen
提出日時	2017-12-13 02:29:16
言語	Java21 (openjdk 21)
結果	WA
実行時間	-
コード長	6,178 bytes
コンパイル時間	2,704 ms
コンパイル使用メモリ	77,884 KB
実行使用メモリ	75,108 KB
最終ジャッジ日時	2023-08-24 13:57:21
合計ジャッジ時間	47,610 ms
ジャッジサーバーID （参考情報）	judge14 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	TLE	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	TLE	-
testcase_35	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.NoSuchElementException;

class Main {
	public static void main(String[] args) {
		//		long t = System.currentTimeMillis();
		new Main().run();
		//		System.out.println(System.currentTimeMillis() - t);
	}

	final long MOD = 1_000_000_000 + 7;
	int n;
	int sqrtN;
	ArrayDeque<Long>[] dq;
	int[] v;
	String[] op;

	void run() {
		Scanner sc = new Scanner();
		n = sc.nextInt();
		n = (n + 1) / 2;
		sqrtN = (int) Math.sqrt(n);
		v = new int[n];
		op = new String[n - 1];
		for (int i = 0; i < n; ++i) {
			v[i] = sc.nextInt();
			if (i != n - 1)
				op[i] = sc.next();
		}
		dq = new ArrayDeque[(int) (n + sqrtN - 1) / sqrtN];
		for (int i = 0; i < dq.length; ++i) {
			dq[i] = new ArrayDeque<>();
			update(i);
		}
		StringBuilder sb = new StringBuilder();
		int Q = sc.nextInt();
		while (Q-- > 0) {
			String T = sc.next();
			int x = sc.nextInt();
			int y = sc.nextInt();
			if (T.equals("?")) {
				x = (x - 1) / 2;
				y = (y - 1) / 2;
				sb.append(query(x, y));
				sb.append("\n");
			} else {
				if (x % 2 == 0) {
					x = x / 2 - 1;
					y = y / 2 - 1;
					if (op[x].equals(op[y]))
						continue;
					{
						String tmp = op[x];
						op[x] = op[y];
						op[y] = tmp;
					}
					update(x / sqrtN);
					update(y / sqrtN);
					if (x != (x + 1) / sqrtN)
						update((x + 1) / sqrtN);
					if (y != (y + 1) / sqrtN)
						update((y + 1) / sqrtN);
				} else {
					x = (x - 1) / 2;
					y = (y - 1) / 2;
					if (x == y)
						continue;
					{
						int tmp = v[y];
						v[y] = v[x];
						v[x] = tmp;
					}
					update(x / sqrtN);
					update(y / sqrtN);
				}
			}
		}
		System.out.println(sb);
	}

	void update(int i) {
		dq[i].clear();
		for (int j = 0; j <= sqrtN - 1 && i * sqrtN + j < n; ++j) {
			int idx = i * sqrtN + j;
			if (j > 0 && op[idx - 1].equals("*")) {
				dq[i].addLast(dq[i].pollLast() * v[idx] % MOD);
			} else {
				while (dq[i].size() >= 3) {
					dq[i].addLast(sum(dq[i].pollLast(), dq[i].pollLast()));
				}
				dq[i].add((long) v[idx]);
			}
		}
	}

	long brute_query(int a, int b) {
		for (int i = a; i <= b; ++i) {
			if (i != a && op[i - 1].equals("*")) {
				ans.addLast(ans.pollLast() * v[i] % MOD);
			} else {
				while (ans.size() >= 3) {
					ans.addLast(sum(ans.pollLast(), ans.pollLast()));
				}
				ans.addLast((long) v[i]);
			}
		}
		long ret = 0;
		for (long ansVal : ans) {
			ret = sum(ret, ansVal);
		}
		return ret;
	}

	ArrayDeque<Long> ans = new ArrayDeque();

	long query(int a, int b) {
		ans.clear();
		if (a / sqrtN == b / sqrtN) {
			for (int i = a; i <= b; ++i) {
				if (i != a && op[i - 1].equals("*")) {
					ans.addLast(ans.pollLast() * v[i] % MOD);
				} else {
					while (ans.size() >= 3) {
						ans.addLast(sum(ans.pollLast(), ans.pollLast()));
					}
					ans.addLast((long) v[i]);
				}
			}
		} else {

			int l = (a + sqrtN - 1) / sqrtN * sqrtN;
			int r = b / sqrtN * sqrtN;
			for (int i = a; i < l; ++i) {
				if (i != a && op[i - 1].equals("*")) {
					ans.addLast(ans.pollLast() * v[i] % MOD);
				} else {
					while (ans.size() >= 3) {
						ans.addLast(sum(ans.pollLast(), ans.pollLast()) % MOD);
					}
					ans.addLast((long) v[i]);
				}
			}
			for (int i = l / sqrtN; i < r / sqrtN; ++i) {
				if (i != a / sqrtN && op[i * sqrtN - 1].equals("*")) {
					ans.addLast(ans.pollLast() * dq[i].peekFirst() % MOD);
				} else {
					while (ans.size() >= 3) {
						ans.addLast(sum(ans.pollLast(), ans.pollLast()));
					}
					ans.add(dq[i].peekFirst());
				}
				boolean first = true;
				for (long v : dq[i]) {
					if (first) {
						first = false;
					} else {
						while (ans.size() >= 3) {
							ans.addLast(sum(ans.pollLast(), ans.pollLast()));
						}
						ans.addLast(v);
					}
				}
			}
			for (int i = r; i <= b; ++i) {
				if (i != a && op[i - 1].equals("*")) {
					ans.addLast(ans.pollLast() * v[i] % MOD);
				} else {
					while (ans.size() >= 3) {
						ans.addLast(sum(ans.pollLast(), ans.pollLast()));
					}
					ans.addLast((long) v[i]);
				}
			}
		}
		long ret = 0;
		for (long ansVal : ans) {
			ret = sum(ret, ansVal);
		}
		return ret;
	}

	long sum(long a, long b) {
		long ret = a + b;
		if (ret >= MOD)
			ret -= MOD;
		return ret;
	}

	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));

	}

	class Scanner {
		private final InputStream in = System.in;
		private final byte[] buffer = new byte[1024];
		private int ptr = 0;
		private int buflen = 0;

		private boolean hasNextByte() {
			if (ptr < buflen) {
				return true;
			} else {
				ptr = 0;
				try {
					buflen = in.read(buffer);
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (buflen <= 0) {
					return false;
				}
			}
			return true;
		}

		private int readByte() {
			if (hasNextByte())
				return buffer[ptr++];
			else
				return -1;
		}

		private boolean isPrintableChar(int c) {
			return 33 <= c && c <= 126;
		}

		public boolean hasNext() {
			while (hasNextByte() && !isPrintableChar(buffer[ptr]))
				ptr++;
			return hasNextByte();
		}

		public String next() {
			if (!hasNext())
				throw new NoSuchElementException();
			StringBuilder sb = new StringBuilder();
			int b = readByte();
			while (isPrintableChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}

		public long nextLong() {
			if (!hasNext())
				throw new NoSuchElementException();
			long n = 0;
			boolean minus = false;
			int b = readByte();
			if (b == '-') {
				minus = true;
				b = readByte();
			}
			if (b < '0' || '9' < b) {
				throw new NumberFormatException();
			}
			while (true) {
				if ('0' <= b && b <= '9') {
					n *= 10;
					n += b - '0';
				} else if (b == -1 || !isPrintableChar(b)) {
					return minus ? -n : n;
				} else {
					throw new NumberFormatException();
				}
				b = readByte();
			}
		}

		public int nextInt() {
			long nl = nextLong();
			if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
				throw new NumberFormatException();
			return (int) nl;
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}
	}
}

yukicoder

結果

テストケース

ソースコード