#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 ispis(){
cout<<Q.size()<<endl;
while(Q.size()){
pp=Q.front();
Q.pop();
cout<<pp.x<<" "<<pp.y<<endl;
}
exit(0);
}
void uradi(int a,int b){
sniz[a]=sniz[a]^sniz[b];
dodaj(a,b);
bool sortiran=true;
for(int i=2;i<=N;i++)
if(niz[i-1]>=niz[i])
sortiran=false;
if(sortiran and Q.size()<=40000)
ispis();
}
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);
isti=true;
for(int i=1;i<=N;i++)
if(sniz[gde].bit[i]!=sta.bit[i])
isti=false;
if(isti)
return;
elem pret;
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;
}
void stavi2(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);
isti=true;
for(int i=1;i<=N;i++)
if(sniz[gde].bit[i]!=sta.bit[i])
isti=false;
if(isti)
return;
elem pret;
for(int i=gde+1;i<=N;i++)
pret.bit[i]=sta.bit[i]^sniz[gde].bit[i];
for(int i=gde;i>=1;i--)
pret.bit[i]=0;
stavi2(gde+1,pret);
uradi(gde,gde+1);
return;
}
void pisibit(){
for(int i=N;i>=1;i--){
for(int j=1;j<=N;j++)
cout<<sniz[j].bit[i]<<" ";
cout<<endl;
}
}
int main(){
// freopen("Input.txt","r",stdin);
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()<=N*N)
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>=2;i--)
stavi1(i,zniz[i]);
if(Q.size()<=N*N)
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-1,k);
uradi(k,k-1);
}
break;
}
//pisibit();
for(int i=1;i<=N;i++)
stavi2(i,zniz[i]);
// pisibit();
if(Q.size()<=N*N)
ispis();
return -1;
}
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 time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
3 ms |
212 KB |
Output is correct |
| 4 |
Correct |
20 ms |
512 KB |
Output is correct |
| 5 |
Correct |
26 ms |
524 KB |
Output is correct |
| 6 |
Correct |
23 ms |
524 KB |
Output is correct |
| 7 |
Correct |
21 ms |
468 KB |
Output is correct |
| 8 |
Correct |
21 ms |
468 KB |
Output is correct |
| 9 |
Correct |
23 ms |
544 KB |
Output is correct |
| 10 |
Correct |
23 ms |
540 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Runtime error |
26 ms |
728 KB |
Execution failed because the return code was nonzero |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Correct |
3 ms |
212 KB |
Output is correct |
| 4 |
Correct |
20 ms |
512 KB |
Output is correct |
| 5 |
Correct |
26 ms |
524 KB |
Output is correct |
| 6 |
Correct |
23 ms |
524 KB |
Output is correct |
| 7 |
Correct |
21 ms |
468 KB |
Output is correct |
| 8 |
Correct |
21 ms |
468 KB |
Output is correct |
| 9 |
Correct |
23 ms |
544 KB |
Output is correct |
| 10 |
Correct |
23 ms |
540 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Runtime error |
26 ms |
728 KB |
Execution failed because the return code was nonzero |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
2 ms |
212 KB |
Output is correct |
| 4 |
Correct |
9 ms |
380 KB |
Output is correct |
| 5 |
Correct |
37 ms |
704 KB |
Output is correct |
| 6 |
Correct |
42 ms |
748 KB |
Output is correct |
| 7 |
Correct |
38 ms |
768 KB |
Output is correct |
| 8 |
Correct |
41 ms |
672 KB |
Output is correct |
| 9 |
Correct |
44 ms |
728 KB |
Output is correct |
| 10 |
Correct |
38 ms |
780 KB |
Output is correct |
| 11 |
Correct |
40 ms |
772 KB |
Output is correct |
| 12 |
Correct |
40 ms |
764 KB |
Output is correct |
| 13 |
Correct |
39 ms |
724 KB |
Output is correct |
| 14 |
Correct |
41 ms |
760 KB |
Output is correct |
| 15 |
Correct |
50 ms |
872 KB |
Output is correct |
