oj.uz

답안 #718048

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
718048 2023-04-03T08:54:16 Z NemanjaSo2005 Xor Sort (eJOI20_xorsort) C++14
40 / 100
 50 ms 872 KB 
#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;
}

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 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 -

Subtask #2
0 / 35.0

# 결과 실행 시간 메모리 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 -

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 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