| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 508534 | 2022-01-13T11:48:41 Z | uncripted | Xor Sort (eJOI20_xorsort) | C++11 | 62 ms | 1016 KB |
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
int power[22];
int pas[40005][3];
int n;
void pow2calc(int x){
power[1]=1;
for(int i=2; i<=x; i++){
power[i]=power[i-1]*2;
}
}
pair<int,int> aa[2000002];
int a1[2000002];
int a[2000005];
int main(){
int s;
pow2calc(21);
cin>>n;
cin>>s;
if(s==1){
int k=0;
for(int i=1; i<=n; i++){
cin>>a[i];
a1[i]=a[i];
aa[i].ff=a[i];
aa[i].ss=i;
}
sort(aa+1, aa+n+1);
int lastsort=n;
while(lastsort!=1){
int maxi=aa[lastsort].ss;
for(int i=1; i<=lastsort-1; i++ ){
k++;
pas[k][1]=i;
pas[k][2]=i+1;
a1[i]=a1[i]^a1[i+1];
}
for(int i=maxi+1; i<=lastsort; i++){
k++;
pas[k][1]=i;
pas[k][2]=i-1;
a1[i]=a1[i]^a1[i-1];
}
for(int i=maxi-2; i>=1; i--){
k++;
pas[k][1]=i;
pas[k][2]=i+1;
a1[i]=a1[i]^a1[i+1];
}
for(int i=1; i<=n; i++){
if(aa[i].ss>maxi){
aa[i].ss--;
}
}
lastsort--;
}
for(int i=n-1; i>=1; i--){
k++;
pas[k][1]=i;
pas[k][2]=i+1;
a1[i]=a1[i]^a1[i+1];
}
cout<<k<<endl;
for(int i=1; i<=k; i++){
cout<<pas[i][1]<<" "<<pas[i][2]<<endl;
}
cout<<endl;
for(int i=1; i<=n; i++){
// cout<<a1[i]<<" ";
}
}
if(s==2){
int ax[n+1];
int k=0;
for(int i=1; i<=n; i++){
cin>>ax[i];
}
int last=n;
for(int i=21; i>=1; i--){
int j=1;
int z=(power[i]&ax[j]);
while((power[i]&ax[j])==0 && j<=n){
j++;
}
if(j==n+1){
continue;
}
for(int jj=j; jj<last; jj++){
if((power[i]&ax[jj])!=0){
if((power[i]&ax[jj+1])==0){
k+=2;
ax[jj+1]=(ax[jj]^a[jj+1]);
ax[jj]=(ax[jj]^ax[jj+1]);
pas[k-1][1]=jj+1;
pas[k-1][2]=jj;
pas[k][1]=jj;
pas[k][2]=jj+1;
}else{
k++;
ax[jj]=(ax[jj]^ax[jj+1]);
pas[k][1]=jj;
pas[k][2]=jj+1;
}
}
}
last--;
}
cout<<k<<endl;
for(int i=1; i<=k; i++){
cout<<pas[i][1]<<" "<<pas[i][2]<<endl;
}
for(int i=1; i<=n; i++){
// cout<<ax[i]<<" ";
}
}
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 204 KB | Output is correct |
| 2 | Correct | 1 ms | 204 KB | Output is correct |
| 3 | Correct | 5 ms | 332 KB | Output is correct |
| 4 | Correct | 28 ms | 716 KB | Output is correct |
| 5 | Correct | 30 ms | 676 KB | Output is correct |
| 6 | Correct | 35 ms | 632 KB | Output is correct |
| 7 | Correct | 30 ms | 652 KB | Output is correct |
| 8 | Correct | 33 ms | 820 KB | Output is correct |
| 9 | Correct | 32 ms | 632 KB | Output is correct |
| 10 | Correct | 32 ms | 672 KB | Output is correct |
| 11 | Correct | 29 ms | 692 KB | Output is correct |
| 12 | Correct | 33 ms | 680 KB | Output is correct |
| 13 | Correct | 34 ms | 716 KB | Output is correct |
| 14 | Correct | 31 ms | 640 KB | Output is correct |
| 15 | Correct | 31 ms | 648 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 204 KB | Output is correct |
| 2 | Correct | 1 ms | 204 KB | Output is correct |
| 3 | Correct | 5 ms | 332 KB | Output is correct |
| 4 | Correct | 28 ms | 716 KB | Output is correct |
| 5 | Correct | 30 ms | 676 KB | Output is correct |
| 6 | Correct | 35 ms | 632 KB | Output is correct |
| 7 | Correct | 30 ms | 652 KB | Output is correct |
| 8 | Correct | 33 ms | 820 KB | Output is correct |
| 9 | Correct | 32 ms | 632 KB | Output is correct |
| 10 | Correct | 32 ms | 672 KB | Output is correct |
| 11 | Correct | 29 ms | 692 KB | Output is correct |
| 12 | Correct | 33 ms | 680 KB | Output is correct |
| 13 | Correct | 34 ms | 716 KB | Output is correct |
| 14 | Correct | 31 ms | 640 KB | Output is correct |
| 15 | Correct | 31 ms | 648 KB | Output is correct |
| 16 | Correct | 0 ms | 204 KB | Output is correct |
| 17 | Correct | 28 ms | 588 KB | Output is correct |
| 18 | Correct | 50 ms | 964 KB | Output is correct |
| 19 | Correct | 57 ms | 932 KB | Output is correct |
| 20 | Correct | 54 ms | 964 KB | Output is correct |
| 21 | Correct | 56 ms | 980 KB | Output is correct |
| 22 | Correct | 62 ms | 908 KB | Output is correct |
| 23 | Correct | 52 ms | 972 KB | Output is correct |
| 24 | Correct | 53 ms | 920 KB | Output is correct |
| 25 | Correct | 52 ms | 976 KB | Output is correct |
| 26 | Correct | 50 ms | 984 KB | Output is correct |
| 27 | Correct | 49 ms | 964 KB | Output is correct |
| 28 | Correct | 58 ms | 1016 KB | Output is correct |
| 29 | Correct | 52 ms | 984 KB | Output is correct |
| 30 | Correct | 54 ms | 972 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 204 KB | Output is correct |
| 2 | Incorrect | 0 ms | 204 KB | Not sorted |
| 3 | Halted | 0 ms | 0 KB | - |