// Muallif: Mansuraliyev Husanboy Murotali o'g'li >> NamPS
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(a) a.begin(), a.end()
#define F first
#define S second
struct segtree{
vector<int> t;
int sz=0;
void init(int n){
t.assign(4*n+1,0);
sz=n;
}
void upd(int x, int l, int r, int ind, int val){
if(l==r){
t[x]=val;return;
}
int m=(l+r)/2;
if(ind>m){
upd(x*2+1,m+1,r,ind,val);
}else upd(x*2,l,m,ind,val);
t[x]=t[x*2]^t[x*2+1];
}
void upd(int ind, int val){
upd(1,1,sz,ind,val);
}
int get(int x, int l, int r, int lx, int rx){
if(lx<=l&&r<=rx){
return t[x];
}
if(r<lx||rx<l){
return 0;
}
int m=(l+r)/2;
return get(x*2,l,m,lx,rx)^get(x*2+1,m+1,r,lx,rx);
}
int get(int l,int r){
return get(1,1,sz,l,r);
}
};
segtree t;
void solve(){
int n,s;
cin>>n>>s;
int a[n],b[n+1];
t.init(n);
for(int i=0;i<n;i++) cin>>a[i];
for(int i=1;i<=n;i++) b[i]=a[i-1],t.upd(i,b[i]);
vector<pair<int,int> > ans;
int mx=1e9;
if(s==1){//cout<<"doe"<<endl;
for(int i=n;i>=1;i--){
int mx2=0,ind=0;
for(int j=1;j<=i;j++){
int cur=t.get(j,i);
if(cur>=mx) continue;
if(cur>mx2) mx2=cur,ind=j;
}//cout<<ind<<"\n";
if(ind==0){
// cout<<"wrong solution";return;
for(int j=i;j<n&&b[j]>b[j+1];j++){
swap(b[j],b[j+1]);
t.upd(j,b[j]); t.upd(j+1,b[j+1]);
ans.push_back({j,j+1});
ans.push_back({j+1,j});
ans.push_back({j,j+1});
}
//cout<<i<<' ';
}else for(int j=ind; j<i;j++){
ans.push_back({j+1,j});
b[j+1]^=b[j];
t.upd(j+1,b[j+1]);
}
mx=b[i];
}
for(int i=1;i<=n;i++) cout<<b[i]<<' ';cout<<endl;
cout<<ans.size()<<"\n";
for(auto u:ans){
cout<<u.F<<' '<<u.S<<"\n";
}
return;
}
int done=0; bool ok=0;
for(int i=19;i>=0;i--){
ok=0;
for(int j=0;j<n-done-1;j++){
if(a[j]&(1<<i)){
ok=1;
if(a[j+1]&(1<<i)){
ans.push_back({j,j+1});
a[j]^=a[j+1];
}else{
ans.push_back({j+1,j});
ans.push_back({j,j+1});
a[j+1]^=a[j];
a[j]^=a[j+1];
}
}
}
done+=ok;
}
cout<<ans.size()<<"\n";
for(auto u:ans){
cout<<u.F+1<<' '<<u.S+1<<"\n";
}
}
int main(){
ios;
//int t=1; cin>>t; while(t--)
solve();
}
Compilation message
xorsort.cpp: In function 'void solve()':
xorsort.cpp:85:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
85 | for(int i=1;i<=n;i++) cout<<b[i]<<' ';cout<<endl;
| ^~~
xorsort.cpp:85:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
85 | for(int i=1;i<=n;i++) cout<<b[i]<<' ';cout<<endl;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Integer 195718 violates the range [0, 40000] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Integer 195718 violates the range [0, 40000] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
2 ms |
468 KB |
Output is correct |
| 5 |
Correct |
8 ms |
864 KB |
Output is correct |
| 6 |
Correct |
6 ms |
852 KB |
Output is correct |
| 7 |
Correct |
6 ms |
852 KB |
Output is correct |
| 8 |
Correct |
5 ms |
852 KB |
Output is correct |
| 9 |
Correct |
7 ms |
848 KB |
Output is correct |
| 10 |
Correct |
8 ms |
936 KB |
Output is correct |
| 11 |
Correct |
6 ms |
852 KB |
Output is correct |
| 12 |
Correct |
6 ms |
944 KB |
Output is correct |
| 13 |
Correct |
5 ms |
980 KB |
Output is correct |
| 14 |
Correct |
7 ms |
980 KB |
Output is correct |
| 15 |
Correct |
8 ms |
1004 KB |
Output is correct |
