Submission #722765

#	Time	Username	Problem	Language	Result	Execution time	Memory
722765		NemanjaSo2005	Xor Sort (eJOI20_xorsort)	C++14	65 / 100	1086 ms	6660 KiB

xorsort

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll N,S,niz[1005],pniz[205],niz2[205],MaxO;
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){
   if(Q.size()>MaxO)
      return;
   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){
   if(Q.size()>MaxO)
      return;
   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];
   MaxO=40000;
   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()<=MaxO)
         ispis();
      while(Q.size())
         Q.pop();
      for(int mbit=0;mbit<=N;mbit++){
         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);
                  if(i<=mbit)
                     uradi(k,k-1);
               }
               break;
            }
         pisibit();
         for(int i=N;i>=2;i--)
            stavi1(i,zniz[i]);

         if(Q.size()<=MaxO)
            ispis();
         while(Q.size())
            Q.pop();
      }
      for(int mbit=1;mbit<=N+1;mbit++){
         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);
                  if(i>=mbit)
                     uradi(k,k-1);
               }
               break;
            }
         pisibit();
         for(int i=N;i>=2;i--)
            stavi1(i,zniz[i]);

         if(Q.size()<=MaxO)
            ispis();
         while(Q.size())
            Q.pop();
      }

/*
      for(int mbit=0;mbit<=N;mbit++){
         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);
                  if(i<=mbit)
                     uradi(k-1,k);
               }
               break;
            }

         //pisibit();

         for(int i=1;i<=N;i++)
            stavi2(i,zniz[i]);

        // pisibit();
         if(Q.size()<=MaxO)
            ispis();
      }

      for(int mbit=1;mbit<=N+1;mbit++){
         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);
                  if(i>=mbit)
                     uradi(k-1,k);
               }
               break;
            }

         //pisibit();

         for(int i=1;i<=N;i++)
            stavi2(i,zniz[i]);

        // pisibit();
         if(Q.size()<=MaxO)
            ispis();
      }*/
      cout<<"0\n";
      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;
}

Compilation message (stderr)

xorsort.cpp: In function 'void stavi1(int, elem)':
xorsort.cpp:46:15: warning: comparison of integer expressions of different signedness: 'std::queue<slog>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   46 |    if(Q.size()>MaxO)
      |       ~~~~~~~~^~~~~
xorsort.cpp: In function 'void stavi2(int, elem)':
xorsort.cpp:75:15: warning: comparison of integer expressions of different signedness: 'std::queue<slog>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   75 |    if(Q.size()>MaxO)
      |       ~~~~~~~~^~~~~
xorsort.cpp: In function 'int main()':
xorsort.cpp:127:18: warning: comparison of integer expressions of different signedness: 'std::queue<slog>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  127 |       if(Q.size()<=MaxO)
      |          ~~~~~~~~^~~~~~
xorsort.cpp:158:21: warning: comparison of integer expressions of different signedness: 'std::queue<slog>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  158 |          if(Q.size()<=MaxO)
      |             ~~~~~~~~^~~~~~
xorsort.cpp:190:21: warning: comparison of integer expressions of different signedness: 'std::queue<slog>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  190 |          if(Q.size()<=MaxO)
      |             ~~~~~~~~^~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 0 / 35
• Subtask 3: 40 / 40