답안 #697948

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
697948	2023-02-11T14:46:34 Z	gagik_2007	XOR (IZhO12_xor)	C++17	100 / 100	173 ms	62284 KB

xor

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;

typedef long long ll;
typedef long double ld;

#define ff first
#define ss second

const ll K = 2;

struct Vertex {
    Vertex* to[K];
    int cnt;
    Vertex() {
        for (ll i = 0; i < K; i++) {
            to[i] = nullptr;
        }
        cnt = 1e8;
    }
};

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 1000007;
const ll LG = 29;
ll n, m, k;
Vertex p;
ll a[N];
ll pf[N];

void add(int x, int vl) {
    Vertex* v = &p;
    (*v).cnt = min((*v).cnt, vl);
    for (int i = LG; i >= 0; i--) {
        //cout << i << endl;
        int c = 0;
        if (x & (1 << i)) {
            c = 1;
        }
        if ((*v).to[c] == nullptr) {
            //cout << "baba";
            (*v).to[c] = new Vertex();
            //cout << "baba";
        }
        v = (*v).to[c];
        (*v).cnt = min((*v).cnt, vl);
    }
}

int get_cnt(int vl) {
    //cout << endl;
    int cur = 0;
    Vertex* v = &p;
    int res = N;
    for (int i = LG; i >= 0; i--) {
        //cout << res << " " << v << endl;
        if (vl & (1 << i)) {
            if (cur + (1 << i) >= k && (*v).to[0] != nullptr) {
                res = min(res, (*(*v).to[0]).cnt);
                if ((*v).to[1] == nullptr) {
                    return res;
                }
                v = (*v).to[1];
            }
            else if ((*v).to[0] != nullptr) {
                cur += (1 << i);
                v = (*v).to[0];
            }
            else if (cur + (1 << i) >= k) {
                v = (*v).to[1];
            }
            else {
                return res;
            }
        }
        else {
            if (cur + (1 << i) >= k && (*v).to[1] != nullptr) {
                //cout << "MT: 1" << endl;
                res = min(res, (*(*v).to[1]).cnt);
                if ((*v).to[0] == nullptr) {
                    return res;
                }
                v = (*v).to[0];
            }
            else if ((*v).to[1] != nullptr) {
                //cout << "MT: 2" << endl;
                cur += (1 << i);
                v = (*v).to[1];
            }
            else if (cur + (1 << i) >= k) {
                //cout << "MT: 3" << endl;
                v = (*v).to[0];
            }
            else {
                //cout << "MT: 4" << endl;
                return res;
            }
        }
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (i == 1)pf[i] = a[i];
        else pf[i] = pf[i - 1] ^ a[i];
    }
    pair<int, int> ans = { -1,0 };
    add(0, 0);
    for (int i = 1; i <= n; i++) {
        int ind = get_cnt(pf[i]);
        //cout << ind << " ";
        ans = max(ans, { i - ind,-ind });
        //cout << ans << endl;
        add(pf[i], i);
        //cout << "AREC";
    }
    cout << -ans.ss + 1 << " " << ans.ff << endl;
    return 0;
}

/// ---- - --------  ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - --------  ------ -------- -- - - -

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	596 KB	Output is correct
5	Correct	6 ms	2132 KB	Output is correct
6	Correct	8 ms	2380 KB	Output is correct
7	Correct	7 ms	2524 KB	Output is correct
8	Correct	9 ms	2644 KB	Output is correct
9	Correct	76 ms	29092 KB	Output is correct
10	Correct	58 ms	29236 KB	Output is correct
11	Correct	56 ms	29084 KB	Output is correct
12	Correct	59 ms	29140 KB	Output is correct
13	Correct	57 ms	29204 KB	Output is correct
14	Correct	61 ms	29160 KB	Output is correct
15	Correct	59 ms	29176 KB	Output is correct
16	Correct	65 ms	29140 KB	Output is correct
17	Correct	156 ms	62284 KB	Output is correct
18	Correct	152 ms	62256 KB	Output is correct
19	Correct	173 ms	62284 KB	Output is correct
20	Correct	150 ms	62276 KB	Output is correct