Submission #1127808
Source Code Expand
#include <cstdio> #include <cstdint> #include <cstdlib> #include <algorithm> #define repeat(i,n) for (int i = 0; (i) < int(n); ++(i)) #define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i)) typedef long long ll; using namespace std; const ll inf = ll(1e18)+9; #define N_MAX 100000 int32_t a[N_MAX]; int32_t xor_acc[N_MAX+1]; int main() { int n, q; scanf("%d%d", &n, &q); repeat (i,n) scanf("%u", &a[i]); xor_acc[0] = 0; repeat (i,n) xor_acc[i+1] = xor_acc[i] ^ a[i]; ll m = - inf; while (q --) { int l, r; scanf("%d%d", &l, &r); if (m == - inf) { -- l; } else { l = (l + abs(m)) % n; r = (r + abs(m)) % n + 1; } int32_t x = xor_acc[r] ^ xor_acc[l]; int32_t d = 0x7fffffff; m = - inf; int i; for (i = l; i < r-1-8; i += 8) { x ^= xor_acc[i]; ll m0 = (d & a[i] ) -(ll) (x ^ xor_acc[i+1]); ll m1 = (d & a[i] & a[i+1] ) -(ll) (x ^ xor_acc[i+2]); ll m2 = (d & a[i] & a[i+1] & a[i+2] ) -(ll) (x ^ xor_acc[i+3]); ll m3 = (d & a[i] & a[i+1] & a[i+2] & a[i+3] ) -(ll) (x ^ xor_acc[i+4]); ll m4 = (d & a[i] & a[i+1] & a[i+2] & a[i+3] & a[i+4] ) -(ll) (x ^ xor_acc[i+5]); ll m5 = (d & a[i] & a[i+1] & a[i+2] & a[i+3] & a[i+4] & a[i+5] ) -(ll) (x ^ xor_acc[i+6]); ll m6 = (d & a[i] & a[i+1] & a[i+2] & a[i+3] & a[i+4] & a[i+5] & a[i+6] ) -(ll) (x ^ xor_acc[i+7]); ll m7 = (d & a[i] & a[i+1] & a[i+2] & a[i+3] & a[i+4] & a[i+5] & a[i+6] & a[i+7]) -(ll) (x ^ xor_acc[i+8]); m0 = max(m0, m1); m2 = max(m2, m3); m4 = max(m4, m5); m6 = max(m6, m7); m0 = max(m0, m2); m4 = max(m4, m6); m0 = max(m0, m4); m = max(m, m0); d &= a[i] & a[i+1] & a[i+2] & a[i+3] & a[i+4] & a[i+5] & a[i+6] & a[i+7]; x ^= xor_acc[i+8]; } for (; i < r-1; ++ i) { d &= a[i]; x ^= a[i]; m = max(m, d -(ll) x); } printf("%lld\n", m); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | J - XORAND |
User | kimiyuki |
Language | C++14 (Clang 3.8.0) |
Score | 0 |
Code Size | 2396 Byte |
Status | TLE |
Exec Time | 4203 ms |
Memory | 2048 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample_01.txt, subtask0_sample_02.txt |
All | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_pow2_01_mini.txt, subtask1_pow2_02_mini.txt, subtask1_pow2_03_OnlyOneLargeSeg.txt, subtask1_pow2_04_UniqueLargeSegs_BitChangesEverytime.txt, subtask1_pow2_05_UniqueLargeSegs.txt, subtask1_pow2_06_randomSegs.txt, subtask1_pow2_07_randomSegs.txt, subtask1_pow2_08_randomSegs.txt, subtask1_pow2_09_x_to_N-x_SegsOnly.txt, subtask1_pow2_10_x_to_N_SegsOnly.txt, subtask1_pow2_11_length_1_3_7_15_31_etc_SegsOnly_BitChangesEverytime.txt, subtask1_pow2_12_1_3_7_15_31_etc_lengthSegsPlusAlpha_BitChangesEverytime.txt, subtask1_random_01.txt, subtask1_random_02.txt, subtask1_result_minmax_01.txt, subtask1_result_minmax_02.txt, subtask1_result_minmax_03.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample_01.txt | AC | 1 ms | 256 KB |
subtask0_sample_02.txt | AC | 1 ms | 256 KB |
subtask1_pow2_01_mini.txt | AC | 3 ms | 256 KB |
subtask1_pow2_02_mini.txt | AC | 3 ms | 256 KB |
subtask1_pow2_03_OnlyOneLargeSeg.txt | TLE | 4203 ms | 1408 KB |
subtask1_pow2_04_UniqueLargeSegs_BitChangesEverytime.txt | TLE | 4203 ms | 1408 KB |
subtask1_pow2_05_UniqueLargeSegs.txt | TLE | 4203 ms | 1408 KB |
subtask1_pow2_06_randomSegs.txt | TLE | 4203 ms | 2048 KB |
subtask1_pow2_07_randomSegs.txt | TLE | 4203 ms | 2048 KB |
subtask1_pow2_08_randomSegs.txt | TLE | 4203 ms | 2048 KB |
subtask1_pow2_09_x_to_N-x_SegsOnly.txt | TLE | 4203 ms | 1664 KB |
subtask1_pow2_10_x_to_N_SegsOnly.txt | TLE | 4203 ms | 1664 KB |
subtask1_pow2_11_length_1_3_7_15_31_etc_SegsOnly_BitChangesEverytime.txt | TLE | 4203 ms | 1664 KB |
subtask1_pow2_12_1_3_7_15_31_etc_lengthSegsPlusAlpha_BitChangesEverytime.txt | TLE | 4203 ms | 1280 KB |
subtask1_random_01.txt | TLE | 4203 ms | 1280 KB |
subtask1_random_02.txt | TLE | 4203 ms | 1280 KB |
subtask1_result_minmax_01.txt | AC | 1 ms | 256 KB |
subtask1_result_minmax_02.txt | AC | 1 ms | 256 KB |
subtask1_result_minmax_03.txt | AC | 1 ms | 256 KB |