This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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()<=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>=2;i--)
stavi1(i,zniz[i]);
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-1,k);
uradi(k,k-1);
}
break;
}
//pisibit();
for(int i=1;i<=N;i++)
stavi2(i,zniz[i]);
// pisibit();
ispis();
}
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |