Submission #2565617
Source Code Expand
#include <cstdio>
#include <vector>
#include <algorithm>
#include <emmintrin.h>
using namespace std;
// pminsd 命令 (32bit整数のmin) の関数化
static inline __m128i __attribute__((always_inline))
_mm_min_epi32(__m128i a, __m128i b) {
__asm__("pminsd %1, %0" : "+x" (a) : "xm" (b));
return a;
}
// 入力された数列
static int32_t a[100008];
// XORの累積和
static int32_t b[100008];
// i番目の要素の次にj番目のビットが0になる要素のテーブル
static int32_t next_table[1000008][32];
int main() {
// 入力の読み込み
int n, q;
scanf("%d%d", &n, &q);
for (int i = 0; i < n; ++i) { scanf("%d", a + i); }
// テーブルの生成
for (int i = 0; i < n; ++i) {
b[i + 1] = b[i] ^ a[i];
}
for (int i = 0; i < 32; ++i) {
int32_t last = n;
for (int j = n - 1; j >= 0; --j) {
next_table[j][i] = last;
if ((a[j] & (1 << i)) == 0) { last = j; }
}
}
// クエリ処理ループ
int32_t m = -1;
while (q--) {
// 入力・スクランブルの除去
int l, r;
scanf("%d%d", &l, &r);
if (m >= 0) {
l = ((int64_t)l + m) % n;
r = ((int64_t)r + m) % n + 1;
}
else {
--l;
}
// 初期値 (k=l+1) を求める
int32_t xor_tail = b[r];
int32_t and_sum = a[l];
int32_t answer = and_sum - (xor_tail ^ b[l + 1]);
const __m128i v_xor_tail = _mm_set1_epi32(xor_tail);
// ANDで結合した値を1ビットずつ変化させる
for (int i = l; i < r - 1; ) {
// 次に値が変化する位置を求めて区間の終端とする
int last = r - 1;
for (int j = 0; j < 32; ++j) {
if (and_sum & (1 << j)) {
last = min(last, next_table[i][j]);
}
}
// 区間内で最小の x_k ^ x_r を求める
int j = i + 1;
int32_t xor_min = xor_tail ^ b[i + 1];
__m128i v_xor_min = _mm_set1_epi32(xor_min);
for (; j + 3 <= last; j += 4) {
const __m128i bj = _mm_loadu_si128((const __m128i *)(b + j));
v_xor_min = _mm_min_epi32(v_xor_min, _mm_xor_si128(bj, v_xor_tail));
}
// 端数処理
for (; j <= last; ++j) {
xor_min = min(xor_min, xor_tail ^ b[j]);
}
// リダクション
v_xor_min = _mm_min_epi32(
v_xor_min, _mm_srli_si128(v_xor_min, 8));
v_xor_min = _mm_min_epi32(
v_xor_min, _mm_srli_si128(v_xor_min, 4));
xor_min = min(xor_min, _mm_cvtsi128_si32(v_xor_min));
answer = max(answer, and_sum - xor_min);
// 区間を進める
and_sum &= a[last];
i = last;
}
printf("%d\n", answer);
m = (answer < 0 ? -answer : answer);
}
return 0;
}
Submission Info
Submission Time
2018-05-26 21:31:08+0900
Task
J - XORAND
User
leaf2326
Language
C++14 (GCC 5.4.1)
Score
100
Code Size
2600 Byte
Status
AC
Exec Time
2177 ms
Memory
16384 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:25:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &q);
^
./Main.cpp:26:50: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for (int i = 0; i < n; ++i) { scanf("%d", a + i); }
^
./Main.cpp:43:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &l, &r);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
100 / 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
128 KB
subtask0_sample_02.txt
AC
1 ms
128 KB
subtask1_pow2_01_mini.txt
AC
2 ms
256 KB
subtask1_pow2_02_mini.txt
AC
2 ms
256 KB
subtask1_pow2_03_OnlyOneLargeSeg.txt
AC
2152 ms
16384 KB
subtask1_pow2_04_UniqueLargeSegs_BitChangesEverytime.txt
AC
2153 ms
16128 KB
subtask1_pow2_05_UniqueLargeSegs.txt
AC
2060 ms
16384 KB
subtask1_pow2_06_randomSegs.txt
AC
739 ms
16256 KB
subtask1_pow2_07_randomSegs.txt
AC
735 ms
16384 KB
subtask1_pow2_08_randomSegs.txt
AC
748 ms
16384 KB
subtask1_pow2_09_x_to_N-x_SegsOnly.txt
AC
1075 ms
16384 KB
subtask1_pow2_10_x_to_N_SegsOnly.txt
AC
1064 ms
16384 KB
subtask1_pow2_11_length_1_3_7_15_31_etc_SegsOnly_BitChangesEverytime.txt
AC
1039 ms
16128 KB
subtask1_pow2_12_1_3_7_15_31_etc_lengthSegsPlusAlpha_BitChangesEverytime.txt
AC
2177 ms
16128 KB
subtask1_random_01.txt
AC
688 ms
15488 KB
subtask1_random_02.txt
AC
685 ms
15488 KB
subtask1_result_minmax_01.txt
AC
0 ms
128 KB
subtask1_result_minmax_02.txt
AC
0 ms
128 KB
subtask1_result_minmax_03.txt
AC
1 ms
128 KB