結果
問題 |
No.1876 Xor of Sum
|
ユーザー |
![]() |
提出日時 | 2022-04-06 14:46:19 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 386 ms / 2,000 ms |
コード長 | 2,121 bytes |
コンパイル時間 | 1,902 ms |
コンパイル使用メモリ | 76,708 KB |
実行使用メモリ | 51,504 KB |
最終ジャッジ日時 | 2024-11-27 18:49:58 |
合計ジャッジ時間 | 9,659 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(); int n = sc.nextInt(); Bit bit = new Bit(); for (int i = 0; i < n; i++) { bit.shiftXOR(sc.nextInt()); } System.out.println(bit.getValue()); } static class Bit { static final int size = 1500000; static final long mask = (1 << 30) - 1; long[] arr; int count = 0; public Bit() { arr = new long[size]; arr[0] = 1; } public void shiftXOR(int val) { count += val; int div = val / 30; int mod = val % 30; for (int i = count / 30; i - div >= 0; i--) { long tmp = arr[i - div]; tmp <<= mod; if (i - div > 0) { tmp |= (arr[i - div - 1] << mod) >> 30; } tmp &= mask; arr[i] ^= tmp; } } public int getValue() { int value = 0; for (int i = 0; i < size; i++) { for (int j = 0; j < 30; j++) { if ((arr[i] & (1L << j)) != 0) { value ^= i * 30 + j; } } } return value; } } } class Scanner { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(""); public Scanner() throws Exception { } public int nextInt() throws Exception { return Integer.parseInt(next()); } public long nextLong() throws Exception { return Long.parseLong(next()); } public double nextDouble() throws Exception { return Double.parseDouble(next()); } public String next() throws Exception { if (!st.hasMoreTokens()) { st = new StringTokenizer(br.readLine()); } return st.nextToken(); } }