제출 #1172281

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172281		benjaminkleyn	XOR (IZhO12_xor)	C++20	0 / 100	9 ms	1864 KiB

xor

#include <bits/stdc++.h>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define ll long long
using namespace std;
vector<int> costs;
int n, x;
const int maxn = 999999999;
bool bitswitch[200000][30];
 
 
pair<int,int> solve(vector<int> a) {
    map<int, int> lol;
    int cur = 0, full = 0, temp;
    pair<int,int> ans = mp(-1, -1);
    lol[0] = 0;
    for (int i: a) {
        full ^= (1 << i);
    }
    //if (a[0] == 2 && a[1] == 1) {
    //    cout << full << '\n';
    //}
    for (int i=0;i<n;i++) {
        for (int j: a) {
            if (bitswitch[i][j]) {
                cur ^= (1 << j);
            }
        }
        if (lol.find(cur) == lol.end()) {
            lol[cur] = i + 1;
        }
        if (lol.find(cur ^ full) != lol.end()) {
            temp = lol[cur ^ full];
            if (ans.ff < i + 2 - temp) {
                ans.ff = i + 1 - temp; ans.ss = temp;
            } else if (ans.ff == i + 2 - temp && ans.ss > temp) {
                ans.ss = temp;
            }
        }
        //if (a[0] == 2 && a[1] == 1) {
        //    cout << cur << (cur ^ full) << " : " << ans.ff << ' ' << ans.ss << '\n';
        //}
    }
    return ans;
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int d1; cin >> n >> x;
    for (int i=0;i<n;i++) {
        cin >> d1;
        costs.pb(d1);
    }
 
 
    for (int i=0;i<n;i++) {
        for (int j=0;j<30;j++) {
            bitswitch[i][j] = (costs[i] >> j) & 1;
        }
    }
 
 
    pair<int,int> realans = mp(-1, -1), tempans;
    vector<int> permvec;
    for (int i=29;i>-1;i--) {
        permvec.pb(i);
        if (((x >> i) & 1) == 0) {
            tempans = solve(permvec);
            if (tempans.ff > realans.ff) {
                realans = tempans;
            } else if (realans.ff == tempans.ff && tempans.ss < realans.ss) {
                realans = tempans;
            }
            permvec.pop_back();
        }
    }
    //for (int i: permvec) {
    //    cout << i << ' ';
    //} cout << '\n';
    tempans = solve(permvec);
    if (tempans.ff > realans.ff) {
        realans = tempans;
    } else if (realans.ff == tempans.ff && tempans.ss < realans.ss) {
        realans = tempans;
    }
 
     
    cout << realans.ss + 1 << ' ' << realans.ff;
}

• Subtask 1: 0 / 100