oj.uz

Submission #640464

# Submission time Handle Problem Language Result Execution time Memory
640464 2022-09-14T17:51:01 Z Urvuk3 Xor Sort (eJOI20_xorsort) C++17
0 / 100
 1 ms 340 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 340 KB Not sorted
4 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 340 KB Not sorted
4 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Not sorted
2 Halted 0 ms 0 KB -