Submission #718044

#TimeUsernameProblemLanguageResultExecution timeMemory
718044NemanjaSo2005Xor Sort (eJOI20_xorsort)C++14
65 / 100
81 ms1228 KiB
#include<bits/stdc++.h> #define ll long long using namespace std; ll N,S,niz[1005],pniz[205],niz2[205]; bool pncmp(int a,int b){ return niz[a]<niz[b]; } struct slog{ int x,y; }pp; struct elem{ bool bit[205]; elem operator ^ (const elem &a){ elem r; for(int i=1;i<=N;i++) r.bit[i]=a.bit[i]^bit[i]; return r; } } sniz[205],zniz[205]; queue<slog> Q; void dodaj(int a,int b){ pp.x=a; pp.y=b; Q.push(pp); } void uradi(int a,int b){ sniz[a]=sniz[a]^sniz[b]; dodaj(a,b); } void ispis(){ cout<<Q.size()<<endl; while(Q.size()){ pp=Q.front(); Q.pop(); cout<<pp.x<<" "<<pp.y<<endl; } exit(0); } void stavi1(int gde,elem sta){ bool isti=true; for(int i=1;i<=N;i++) if(sniz[gde].bit[i]!=sta.bit[i]) isti=false; if(isti) return; if(sta.bit[gde-1]==sniz[gde].bit[gde-1]) uradi(gde,gde-1); elem pret; isti=true; for(int i=1;i<=N;i++) if(sniz[gde].bit[i]!=sta.bit[i]) isti=false; if(isti) return; for(int i=1;i<gde;i++) pret.bit[i]=sta.bit[i]^sniz[gde].bit[i]; for(int i=gde;i<=N;i++) pret.bit[i]=0; stavi1(gde-1,pret); uradi(gde,gde-1); return; } int main(){ cin>>N>>S; for(int i=1;i<=N;i++) cin>>niz[i]; if(S==1){/* for(int i=1;i<=N;i++) niz2[i]=niz[i]; for(int i=1;i<=N;i++) for(int j=1;j<N;j++) if(niz2[j]>niz2[j+1]){ swap(niz2[j+1],niz2[j]); dodaj(j,j+1); dodaj(j+1,j); dodaj(j,j+1); } if(Q.size()<=40000) ispis(); while(Q.size()) Q.pop();*/ for(int i=1;i<=N;i++) pniz[i]=i; sort(pniz+1,pniz+1+N,pncmp); for(int i=1;i<=N;i++){ sniz[pniz[i]].bit[i]=1; zniz[i].bit[i]=1; } for(int i=1;i<=N;i++) niz2[pniz[i]]=i; for(int i=1;i<=N;i++) for(int j=i;j<=N;j++){ if(niz2[j]!=i) continue; for(int k=j;k>i;k--){ swap(niz2[k],niz2[k-1]); uradi(k,k-1); uradi(k-1,k); } break; } /*for(int i=N;i>=1;i--){ for(int j=1;j<=N;j++) cout<<sniz[j].bit[i]<<" "; cout<<endl; }*/ for(int i=N;i>=2;i--) stavi1(i,zniz[i]); /* cout<<endl; for(int i=N;i>=1;i--){ for(int j=1;j<=N;j++) cout<<sniz[j].bit[i]<<" "; cout<<endl; }*/ ispis(); return 0; } for(int step=(1<<19);step>=1;step/=2){ bool nemoj=true; for(int i=1;i<=N;i++) if(niz[i]&step) nemoj=false; if(nemoj) continue; for(int i=1;i<N;i++) if((niz[i]&step)>0 and (niz[i+1]&step)==0){ niz[i+1]^=niz[i]; dodaj(i+1,i); } for(int i=1;i<N;i++){ if(niz[i]&step){ niz[i]^=niz[i+1]; dodaj(i,i+1); } } N--; } ispis(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...