QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#305843#5434. Binary SubstringsNemanjaSo2005WA 7ms29876kbC++142.0kb2024-01-16 03:41:422024-01-16 03:41:44

Judging History

你现在查看的是最新测评结果

  • [2024-01-16 03:41:44]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:29876kb
  • [2024-01-16 03:41:42]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int N,M,K;
vector<int> graf[(1<<20)+5];
int perm[(1<<20)+5];
void napravi(int k){
   M=1<<(k-1);
   for(int i=0;i<(1<<(k));i++){
      int a=i>>1;
      int b=i&((1<<(k-1))-1);
      graf[a].push_back(b);
   }
}
vector<int> V,R;
void poperm(int gde){
   R.push_back(gde);
   if(perm[gde]==0)
      return;
   int p=perm[gde];
   perm[gde]=0;
   poperm(p);
}
void euler(int gde){
   while(graf[gde].size()){
      int ko=graf[gde].back();
      graf[gde].pop_back();
      euler(ko);
   }
   V.push_back(gde);
}
int main(){
   cin>>N;
   if(N==1){
      cout<<"0\n";
      return 0;
   }
   if(N==2){
      cout<<"01\n";
      return 0;
   }
   if(N==3){
      cout<<"010\n";
      return 0;
   }
   if(N==4){
      cout<<"1001\n";
      return 0;
   }
   for(int i=0;i<=20;i++){
      if((1<<i)+i-1<=N)
         K=i;
   }
  // cout<<"DUZINA JE "<<K<<endl;
   napravi(K);
   /*for(int i=0;i<M;i++){
      cout<<i<<": ";
      for(int p:graf[i])
         cout<<p<<" ";
      cout<<endl;
   }*/
   euler(0);
   reverse(V.begin(),V.end());
   /*cout<<"CIKLUS: ";
   for(int i=0;i<V.size();i++)
      cout<<V[i]<<" ";
   cout<<endl;*/

   if(((1<<(K))+K-1)!=N){
      vector<int> B;
      for(int i=1;i<V.size();i++)
         B.push_back((V[i-1]<<1) + (V[i]&1));
/*
      cout<<"NIZ B:"<<endl;
      for(int i=0;i<B.size();i++)
         cout<<B[i]<<" ";
      cout<<endl;*/

      B.push_back(B[0]);
      for(int i=0;i+1<B.size();i++)
         perm[B[i]]=B[i+1]^1;
      for(int i=0;i+1<B.size();i++)
         poperm(B[i]);
   }
   else{
      //cout<<"OVAKAV"<<endl;
      for(int i=1;i<K;i++)
         cout<<"0";
      for(int i=1;i<V.size();i++)
         cout<<(V[i]&1);
      cout<<endl;
      return 0;
   }
   for(int i=1;i<K;i++)
      cout<<"0";
   for(int i=1;i<=N-(K-1);i++)
      cout<<(R[i]&1);
   cout<<"\n";
   return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 28724kb

input:

2

output:

01

result:

ok meet maximum 3

Test #2:

score: 0
Accepted
time: 2ms
memory: 28480kb

input:

5

output:

01100

result:

ok meet maximum 12

Test #3:

score: 0
Accepted
time: 3ms
memory: 28772kb

input:

1

output:

0

result:

ok meet maximum 1

Test #4:

score: 0
Accepted
time: 0ms
memory: 29876kb

input:

3

output:

010

result:

ok meet maximum 5

Test #5:

score: 0
Accepted
time: 0ms
memory: 28900kb

input:

4

output:

1001

result:

ok meet maximum 8

Test #6:

score: 0
Accepted
time: 3ms
memory: 29460kb

input:

6

output:

001110

result:

ok meet maximum 16

Test #7:

score: 0
Accepted
time: 0ms
memory: 29824kb

input:

7

output:

0011100

result:

ok meet maximum 21

Test #8:

score: 0
Accepted
time: 3ms
memory: 29016kb

input:

8

output:

00111000

result:

ok meet maximum 27

Test #9:

score: -100
Wrong Answer
time: 7ms
memory: 29784kb

input:

9

output:

001110000

result:

wrong answer not meet maximum 33 < 34