Submission #640464

#	Time	Username	Problem	Language	Result	Execution time	Memory
640464		Urvuk3	Xor Sort (eJOI20_xorsort)	C++17	0 / 100	1 ms	340 KiB

xorsort

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int INF=1e9;
const ll LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define PRINT(x) cerr<<#x<<'='<<x<<endl;
#define pb push_back
#define PRINTvec(niz) { cerr<<#niz<<"="; for(auto _i:niz) cerr<<_i<<" "; cerr<<endl; }

void Solve(){
    int N,S; cin>>N>>S;
    vector<int> a(N+1); for(int i=1;i<=N;i++) cin>>a[i];
    set<int> s;
    vector<pii> opers;

    function<void(int,int)> Oper=[&](int i,int j){
        a[i]=a[i]^a[j];
        opers.pb({i,j});
    };
    function<bool(int,int)> Has=[&](int x,int bit){
        return (x&(1<<bit))>0;
    };
    function<void(int,int,int)> Update=[&](int i,int j,int bit){
        if(!Has(a[i],bit) && s.count(i)) s.erase(i);
        if(!Has(a[j],bit) && s.count(j)) s.erase(j);
        if(Has(a[i],bit)) s.insert(i);
        if(Has(a[j],bit)) s.insert(j);
    };

    int L=1,R=N;
    if(S==2){
        for(int bit=20;bit>=0;bit--){
            s.clear();
            bool pomeren=false;
            for(int i=L;i<=R;i++){
                if(Has(a[i],bit)){
                    s.insert(i);
                }
            }
            while(!s.empty() && !(sz(s)==1 && s.count(L))){
                int i=*(prev(s.end()));
                if(Has(a[i-1],bit)){
                    Oper(i,i-1); Update(i-1,i,bit);
                }
                else{
                    Oper(i-1,i); Update(i-1,i,bit);
                    Oper(i,i-1); Update(i-1,i,bit);
                }
            }
            if(pomeren) ++L;
        }
    }
    else{
        for(int bit=20;bit>=0;bit--){
            s.clear();
            bool pomeren=false;
            for(int i=L;i<=R;i++){
                if(Has(a[i],bit)){
                    s.insert(i);
                    pomeren=true;
                }
            }
            while(!s.empty() && !(sz(s)==1 && s.count(R))){
                int i=*(s.begin());
                if(Has(a[i+1],bit)){
                    Oper(i,i+1); Update(i,i+1,bit);
                }
                else{
                    Oper(i+1,i); Update(i,i+1,bit);
                    Oper(i,i+1); Update(i,i+1,bit);
                }
            }
            if(pomeren) --R;
        }
    }
    cout<<sz(opers)<<endl;
    for(auto p:opers) cout<<p.fi<<" "<<p.se<<endl;
    //PRINT(is_sorted(all(a)));
}

/*
50 1
424445 865543 549233 320875 96010 607467 991872 328432 985251 638414 1005454 1009303 1005173 492034 71293 32110 687752 766958 208536 525200 775285 583557 757075 135922 350458 260362 448850 33853 102149 423632 828404 526594 240599 329061 847469 336609 936528 790765 665041 873203 380603 621920 833930 337201 65378 905223 369311 753130 623606 577847
*/

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    //cin>>t;
    t=1;
    while(t--){
        Solve();
    }
    return 0;
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 35
• Subtask 3: 0 / 40