oj.uz

Submission #173665

# Submission time Handle Problem Language Result Execution time Memory
173665 2020-01-04T21:47:57 Z RafaelSus "The Lyuboyn" code (IZhO19_lyuboyn) C++14
100 / 100
 163 ms 7664 KB 
#include <bits/stdc++.h>
 
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
const ll inf=1e15;
#define pb push_back
const int INF=(0x3f3f3f3f);

int tod(vector<int>a){
  int res=0;
  reverse(a.begin(),a.end());
  for(int i=0;i<a.size();i++){
    res+=a[i]*(1<<i);
  }
  return res;
}

int tod(string s){
  int res=0;
  reverse(s.begin(),s.end());
  for(int i=0;i<s.size();i++){
    res+=(s[i]-'0')*(1<<i);
  }
  return res;
}

string tobin(int x,int h){
  string res="";
  if(x==0){
    res="0";
    while(res.size()<h)res+="0";
    return res;
  }
  while(x){
    if(x%2)res+="1";
    else res+="0";
    x/=2;
  }
  while(res.size()<h)res+="0";
  reverse(res.begin(),res.end());
  return res;
}
int n,k,t;

int used[(1<<18)+5];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  
  
  cin>>n>>k>>t;
  string s;
  cin>>s;
  int x=tod(s);
  vector<int>a(n,0);
  for(int i=0;i<k;i++){
    a[n-1-i]=1;
  }
  if(k%2==0){
    cout<<"-1";
    return 0;  
  }
  used[x]=1;
  vector<int>answ;
  answ.pb(x);
  int tmp=x;
  int tim=0,hin=0;
  int X=0;
  while(answ.size()<(1<<n)){
    do{
      if(answ.size()==(1<<n))break;
      int y=tod(a);
      if(!used[y^tmp]){
        answ.pb(y^tmp);
        tmp^=y;
        used[tmp]=1;
        break;
      }
    }while(next_permutation(a.begin(),a.end()));
    for(int i=0;i<(n-k);i++)a[i]=0;
    for(int i=n-k;i<n;i++)a[i]=1;
    if(tim==answ.size()&&tim==hin&&X==10)break;
    if(tim==answ.size()){X++;hin=tim;}
    tim=answ.size();
  }
  if(answ.size()!=(1<<n)){
    cout<<"-1\n";
    return 0;
  }
  cout<<(1<<n)<<'\n';
  for(int i=0;i<answ.size();i++){
    cout<<tobin(answ[i],n)<<'\n';
  }
}

Compilation message

lyuboyn.cpp: In function 'int tod(std::vector<int>)':
lyuboyn.cpp:13:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<a.size();i++){
               ~^~~~~~~~~
lyuboyn.cpp: In function 'int tod(std::__cxx11::string)':
lyuboyn.cpp:22:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<s.size();i++){
               ~^~~~~~~~~
lyuboyn.cpp: In function 'std::__cxx11::string tobin(int, int)':
lyuboyn.cpp:32:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(res.size()<h)res+="0";
           ~~~~~~~~~~^~
lyuboyn.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(res.size()<h)res+="0";
         ~~~~~~~~~~^~
lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:71:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(answ.size()<(1<<n)){
         ~~~~~~~~~~~^~~~~~~
lyuboyn.cpp:73:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(answ.size()==(1<<n))break;
          ~~~~~~~~~~~^~~~~~~~
lyuboyn.cpp:84:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(tim==answ.size()&&tim==hin&&X==10)break;
        ~~~^~~~~~~~~~~~~
lyuboyn.cpp:85:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(tim==answ.size()){X++;hin=tim;}
        ~~~^~~~~~~~~~~~~
lyuboyn.cpp:88:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(answ.size()!=(1<<n)){
      ~~~~~~~~~~~^~~~~~~~
lyuboyn.cpp:93:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<answ.size();i++){
               ~^~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Ok

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Ok

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Ok
2 Correct 2 ms 376 KB Ok
3 Correct 2 ms 376 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 2 ms 380 KB Ok
7 Correct 2 ms 376 KB Ok
8 Correct 2 ms 376 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 7532 KB Ok
2 Correct 65 ms 3956 KB Ok
3 Correct 2 ms 424 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 376 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Ok
2 Correct 5 ms 632 KB Ok
3 Correct 72 ms 3828 KB Ok
4 Correct 37 ms 2168 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 3 ms 376 KB Ok
7 Correct 18 ms 1400 KB Ok
8 Correct 2 ms 376 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 7456 KB Ok
2 Correct 150 ms 7536 KB Ok
3 Correct 146 ms 7532 KB Ok
4 Correct 71 ms 3956 KB Ok
5 Correct 73 ms 3956 KB Ok
6 Correct 36 ms 2168 KB Ok
7 Correct 32 ms 2168 KB Ok
8 Correct 17 ms 1272 KB Ok
9 Correct 17 ms 1272 KB Ok
10 Correct 9 ms 760 KB Ok
11 Correct 2 ms 380 KB Ok
12 Correct 2 ms 376 KB Ok
13 Correct 2 ms 376 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 7532 KB Ok
2 Correct 65 ms 3956 KB Ok
3 Correct 2 ms 424 KB Ok
4 Correct 2 ms 376 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 2 ms 376 KB Ok
7 Correct 5 ms 632 KB Ok
8 Correct 72 ms 3828 KB Ok
9 Correct 37 ms 2168 KB Ok
10 Correct 2 ms 376 KB Ok
11 Correct 3 ms 376 KB Ok
12 Correct 18 ms 1400 KB Ok
13 Correct 2 ms 376 KB Ok
14 Correct 149 ms 7456 KB Ok
15 Correct 150 ms 7536 KB Ok
16 Correct 146 ms 7532 KB Ok
17 Correct 71 ms 3956 KB Ok
18 Correct 73 ms 3956 KB Ok
19 Correct 36 ms 2168 KB Ok
20 Correct 32 ms 2168 KB Ok
21 Correct 17 ms 1272 KB Ok
22 Correct 17 ms 1272 KB Ok
23 Correct 9 ms 760 KB Ok
24 Correct 2 ms 380 KB Ok
25 Correct 2 ms 376 KB Ok
26 Correct 2 ms 376 KB Ok
27 Correct 145 ms 7540 KB Ok
28 Correct 70 ms 3960 KB Ok
29 Correct 137 ms 7460 KB Ok
30 Correct 9 ms 760 KB Ok
31 Correct 2 ms 376 KB Ok
32 Correct 5 ms 504 KB Ok
33 Correct 16 ms 1400 KB Ok
34 Correct 2 ms 376 KB Ok
35 Correct 2 ms 376 KB Ok
36 Correct 3 ms 376 KB Ok
37 Correct 2 ms 376 KB Ok
38 Correct 71 ms 3952 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 3828 KB Ok
2 Correct 163 ms 7484 KB Ok
3 Correct 136 ms 7532 KB Ok
4 Correct 9 ms 760 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 16 ms 1272 KB Ok
7 Correct 151 ms 7664 KB Ok
8 Correct 3 ms 376 KB Ok
9 Correct 2 ms 376 KB Ok
10 Correct 3 ms 376 KB Ok
11 Correct 36 ms 2168 KB Ok
12 Correct 72 ms 3924 KB Ok