oj.uz

Submission #168294

# Submission time Handle Problem Language Result Execution time Memory
168294 2019-12-12T09:59:54 Z Nordway "The Lyuboyn" code (IZhO19_lyuboyn) C++14
100 / 100
 307 ms 20996 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define up_b upper_bound
#define low_b lower_bound
#define nl '\n'

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;

const int N=19;
const int M=1e6+11;
const int inf=1e9;
const ll INF=1e18;
const ll mod=1e9+7;
const double EPS=1e-9;

vector<int>v;
int used[(1<<N)];
int p[(1<<N)];
int a;
int n,k,t;

void answer(int val){
  vector<int>ans;
  while(val!=a){
    ans.pb(val);
    val=p[val];
  }
  ans.pb(a);
  reverse(all(ans));
  cout<<sz(ans)<<nl;
  for(int i=0;i<sz(ans);i++){
    for(int j=n-1;j>=0;j--){
      cout<<((ans[i]>>j)&1);
    }
    cout<<nl;
  }
  exit(0);
}

void go(int val,int i){
  if(i==(1<<n)){
    if(t==1){
      if(__builtin_popcount(a^val)==k){
        answer(val);
      }
    }
    else{
      answer(val);
    }
    return ;
  }
  for(int j=0;j<sz(v);j++){
    int to=(v[j]^val);
    if(!used[to]){
      used[to]=1;
      p[to]=val;
      go(to,i+1);
      used[to]=0;
    }
  }
}

int main(){
  cin>>n>>k>>t;
  string s;
  cin>>s;
  reverse(all(s));
  for(int i=0;i<sz(s);i++){
    a+=(1<<i)*(s[i]-'0');
  }
  for(int i=0;i<(1<<n);i++){
    if(__builtin_popcount(i)==k){
      v.pb(i);
    }
  }
  if(k%2==0)cout<<"-1";
  else{
    used[a]=1;
    go(a,1);
  }
}

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 3 ms 256 KB Ok
3 Correct 3 ms 632 KB Ok
4 Correct 2 ms 256 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 2 ms 376 KB Ok
7 Correct 2 ms 376 KB Ok
8 Correct 3 ms 376 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 20892 KB Ok
2 Correct 141 ms 10480 KB Ok
3 Correct 2 ms 376 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 9 ms 888 KB Ok
3 Correct 145 ms 10580 KB Ok
4 Correct 67 ms 5492 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 3 ms 504 KB Ok
7 Correct 33 ms 3064 KB Ok
8 Correct 2 ms 376 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 20996 KB Ok
2 Correct 292 ms 20864 KB Ok
3 Correct 293 ms 20924 KB Ok
4 Correct 141 ms 10864 KB Ok
5 Correct 140 ms 10592 KB Ok
6 Correct 67 ms 5620 KB Ok
7 Correct 67 ms 5492 KB Ok
8 Correct 33 ms 2936 KB Ok
9 Correct 33 ms 2936 KB Ok
10 Correct 17 ms 1656 KB Ok
11 Correct 3 ms 376 KB Ok
12 Correct 3 ms 380 KB Ok
13 Correct 2 ms 376 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 20892 KB Ok
2 Correct 141 ms 10480 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 376 KB Ok
7 Correct 9 ms 888 KB Ok
8 Correct 145 ms 10580 KB Ok
9 Correct 67 ms 5492 KB Ok
10 Correct 2 ms 376 KB Ok
11 Correct 3 ms 504 KB Ok
12 Correct 33 ms 3064 KB Ok
13 Correct 2 ms 376 KB Ok
14 Correct 291 ms 20996 KB Ok
15 Correct 292 ms 20864 KB Ok
16 Correct 293 ms 20924 KB Ok
17 Correct 141 ms 10864 KB Ok
18 Correct 140 ms 10592 KB Ok
19 Correct 67 ms 5620 KB Ok
20 Correct 67 ms 5492 KB Ok
21 Correct 33 ms 2936 KB Ok
22 Correct 33 ms 2936 KB Ok
23 Correct 17 ms 1656 KB Ok
24 Correct 3 ms 376 KB Ok
25 Correct 3 ms 380 KB Ok
26 Correct 2 ms 376 KB Ok
27 Correct 307 ms 20948 KB Ok
28 Correct 144 ms 10548 KB Ok
29 Correct 294 ms 20956 KB Ok
30 Correct 16 ms 1528 KB Ok
31 Correct 3 ms 376 KB Ok
32 Correct 9 ms 888 KB Ok
33 Correct 34 ms 2960 KB Ok
34 Correct 2 ms 376 KB Ok
35 Correct 2 ms 376 KB Ok
36 Correct 2 ms 376 KB Ok
37 Correct 2 ms 376 KB Ok
38 Correct 146 ms 10500 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 10480 KB Ok
2 Correct 307 ms 20836 KB Ok
3 Correct 295 ms 20972 KB Ok
4 Correct 17 ms 1656 KB Ok
5 Correct 2 ms 376 KB Ok
6 Correct 34 ms 2940 KB Ok
7 Correct 294 ms 20868 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 70 ms 5492 KB Ok
12 Correct 142 ms 10480 KB Ok