제출 #1186166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1186166		Hanksburger	XOR (IZhO12_xor)	C++20	100 / 100	53 ms	45188 KiB

xor

#include <bits/stdc++.h>
using namespace std;
int n, m;
pair<int, int> mx(pair<int, int> x, pair<int, int> y)
{
    if (x.second>y.second)
        return x;
    else if (x.second<y.second)
        return y;
    else if (x.first<y.first)
        return x;
    else
        return y;
}
pair<int, int> recur(vector<pair<int, int> > u, vector<pair<int, int> > v, int ind)
{
    if (u.empty() || v.empty())
        return {0, 0};
    if (ind==-1)
    {
        int umn=1e9, umx=-1e9, vmn=1e9, vmx=-1e9;
        for (int i=0; i<u.size(); i++)
        {
            umn=min(umn, u[i].first);
            umx=max(umx, u[i].first);
        }
        for (int i=0; i<v.size(); i++)
        {
            vmn=min(vmn, v[i].first);
            vmx=max(vmx, v[i].first);
        }
        return mx({umn, vmx-umn}, {vmn, umx-vmn});
    }
    vector<pair<int, int> > u0, u1, v0, v1;
    for (int i=0; i<u.size(); i++)
    {
        if (u[i].second&(1<<ind))
            u1.push_back(u[i]);
        else
            u0.push_back(u[i]);
    }
    for (int i=0; i<v.size(); i++)
    {
        if (v[i].second&(1<<ind))
            v1.push_back(v[i]);
        else
            v0.push_back(v[i]);
    }
    if (m&(1<<ind))
        return mx(recur(u1, v0, ind-1), recur(u0, v1, ind-1));
    return mx(mx(recur(u1, v0, -1), recur(u0, v1, -1)), mx(recur(u0, v0, ind-1), recur(u1, v1, ind-1)));
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    vector<pair<int, int> > v;
    v.push_back({0, 0});
    for (int i=1; i<=n; i++)
    {
        int x;
        cin >> x;
        v.push_back({i, v.back().second^x});
    }
    pair<int, int> ans=recur(v, v, 29);
    cout << ans.first+1 << ' ' << ans.second;
}

• Subtask 1: 100 / 100