code festival 2014 上海

Submission #1127869

Source codeソースコード

#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))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(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 and_skip[N_MAX][31];
int main() {
    // input
    int n, q; scanf("%d%d", &n, &q);
    repeat (i,n) scanf("%u", &a[i]);
    { // prepare
        xor_acc[0] = 0;
        repeat (i,n) xor_acc[i+1] = xor_acc[i] ^ a[i];
        repeat (k,31) and_skip[n-1][k] = n;
        repeat_reverse (i,n-1) {
            repeat (k,31) {
                and_skip[i][k] = and_skip[i+1][k];
                if (not (a[i+1] & (1<<k))) and_skip[i][k] = i+1;
            }
        }
    }
    // query
    ll m = - inf;
    while (q --) {
        // input
        int l, r; scanf("%d%d", &l, &r);
        if (m == - inf) {
            -- l;
        } else {
            l = (l + abs(m)) % n;
            r = (r + abs(m)) % n + 1;
        }
        // solve
        m = - inf;
        int32_t d = a[l];
        for (int i = l; i < r-1; ) {
            int ni = r-1;
            repeat (k,31) if (d & (1<<k)) ni = min(ni, and_skip[i][k]);
            int32_t x = 0x7fffffff;
            repeat_from (j,i,ni) {
                x = min(x, xor_acc[r] ^ xor_acc[j+1]);
            }
            m = max(m, d -(ll) x);
            d &= a[ni];
            i = ni;
        }
        // output
        printf("%lld\n", m);
    }
    return 0;
}

Submission

Task問題 J - XORAND
User nameユーザ名 うさぎ
Created time投稿日時
Language言語 C++14 (Clang 3.8.0)
Status状態 AC
Score得点 100
Source lengthソースコード長 1618 Byte
File nameファイル名
Exec time実行時間 2456 ms
Memory usageメモリ使用量 14208 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0_sample_01.txt,subtask0_sample_02.txt
All 100 / 100 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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 384 KB
subtask1_pow2_02_mini.txt AC 3 ms 384 KB
subtask1_pow2_03_OnlyOneLargeSeg.txt AC 2401 ms 14208 KB
subtask1_pow2_04_UniqueLargeSegs_BitChangesEverytime.txt AC 2434 ms 14080 KB
subtask1_pow2_05_UniqueLargeSegs.txt AC 2303 ms 14208 KB
subtask1_pow2_06_randomSegs.txt AC 851 ms 14080 KB
subtask1_pow2_07_randomSegs.txt AC 848 ms 14208 KB
subtask1_pow2_08_randomSegs.txt AC 860 ms 14208 KB
subtask1_pow2_09_x_to_N-x_SegsOnly.txt AC 1237 ms 14208 KB
subtask1_pow2_10_x_to_N_SegsOnly.txt AC 1230 ms 14208 KB
subtask1_pow2_11_length_1_3_7_15_31_etc_SegsOnly_BitChangesEverytime.txt AC 1198 ms 14080 KB
subtask1_pow2_12_1_3_7_15_31_etc_lengthSegsPlusAlpha_BitChangesEverytime.txt AC 2456 ms 13952 KB
subtask1_random_01.txt AC 797 ms 13312 KB
subtask1_random_02.txt AC 793 ms 13312 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