oj.uz

Submission #895635

# Submission time Handle Problem Language Result Execution time Memory
895635 2023-12-30T12:20:58 Z mychecksedad "The Lyuboyn" code (IZhO19_lyuboyn) C++17
100 / 100
 534 ms 6840 KB 
/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;

int n, k, t, b = 0;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve(){
  cin >> n >> k >> t;
  for(int i = n-1; i >= 0; --i){
    char c; cin >> c;
    b += (1<<i)*(c=='1');
  }
  vector<int> s, base;

  for(int i = 0; i < (1<<n); ++i) if(__builtin_popcount(i) == k) base.pb(i);

  bool ok = 0;

  int sz = base.size() - 1;

  for(int rep = 0; rep < 200; ++rep){
    vector<bool> used(1<<n);
    s.clear();
    used[0] = 1;
    for(int j = 0; j < n; ++j){
      int mask = 0;
      while(used[mask]){
        mask = base[uniform_int_distribution<int>(0,sz)(rng)];
      }
      s.pb(mask);
      used[mask] = 1;
    }
    ok = 1;
    for(int mask = 1; mask < (1<<n); ++mask){
      int x = 0;
      for(int j = 0; j < n; ++j){
        if((1<<j)&mask){
          x ^= s[j];
        }
      }
      if(x == 0){
        ok = 0;
        break;
      }
    }
    if(ok) break;
  }
  if(!ok){
    cout << -1;
    return;
  }
  // for(int x: s) cout << x << ' ';
  vector<int> cur;
  cur.pb(0);
  for(int i = 0; i < n; ++i){
    vector<int> t;
    for(int j = cur.size() - 1; j >= 0; --j){
      t.pb(cur[j]^s[i]);
    }
    for(int x: t) cur.pb(x);
  }
  cout << (1<<n) << '\n';
  for(int x: cur){
    int num = x^b;
    for(int j = (n-1); j >= 0; --j){
      cout << (((1<<j)&num)>0);
    }
    en;
  }
}



int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // cin >> tt;
  while(tt--){
    solve();
    // en;
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
}

Compilation message

lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:83:15: warning: unused variable 'aa' [-Wunused-variable]
   83 |   int tt = 1, aa;
      |               ^~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Ok

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Ok

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 348 KB Ok
2 Correct 342 ms 464 KB Ok
3 Correct 534 ms 656 KB Ok
4 Correct 0 ms 348 KB Ok
5 Correct 2 ms 456 KB Ok
6 Correct 19 ms 452 KB Ok
7 Correct 31 ms 348 KB Ok
8 Correct 518 ms 496 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 6632 KB Ok
2 Correct 86 ms 3416 KB Ok
3 Correct 1 ms 348 KB Ok
4 Correct 0 ms 348 KB Ok
5 Correct 0 ms 348 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Ok
2 Correct 5 ms 604 KB Ok
3 Correct 120 ms 3268 KB Ok
4 Correct 75 ms 1744 KB Ok
5 Correct 1 ms 348 KB Ok
6 Correct 1 ms 348 KB Ok
7 Correct 20 ms 1116 KB Ok
8 Correct 0 ms 348 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 6840 KB Ok
2 Correct 186 ms 6708 KB Ok
3 Correct 190 ms 6424 KB Ok
4 Correct 124 ms 3620 KB Ok
5 Correct 124 ms 3652 KB Ok
6 Correct 52 ms 1768 KB Ok
7 Correct 41 ms 1796 KB Ok
8 Correct 20 ms 1112 KB Ok
9 Correct 21 ms 1372 KB Ok
10 Correct 10 ms 860 KB Ok
11 Correct 1 ms 348 KB Ok
12 Correct 1 ms 348 KB Ok
13 Correct 0 ms 548 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 6632 KB Ok
2 Correct 86 ms 3416 KB Ok
3 Correct 1 ms 348 KB Ok
4 Correct 0 ms 348 KB Ok
5 Correct 0 ms 348 KB Ok
6 Correct 0 ms 348 KB Ok
7 Correct 5 ms 604 KB Ok
8 Correct 120 ms 3268 KB Ok
9 Correct 75 ms 1744 KB Ok
10 Correct 1 ms 348 KB Ok
11 Correct 1 ms 348 KB Ok
12 Correct 20 ms 1116 KB Ok
13 Correct 0 ms 348 KB Ok
14 Correct 202 ms 6840 KB Ok
15 Correct 186 ms 6708 KB Ok
16 Correct 190 ms 6424 KB Ok
17 Correct 124 ms 3620 KB Ok
18 Correct 124 ms 3652 KB Ok
19 Correct 52 ms 1768 KB Ok
20 Correct 41 ms 1796 KB Ok
21 Correct 20 ms 1112 KB Ok
22 Correct 21 ms 1372 KB Ok
23 Correct 10 ms 860 KB Ok
24 Correct 1 ms 348 KB Ok
25 Correct 1 ms 348 KB Ok
26 Correct 0 ms 548 KB Ok
27 Correct 187 ms 6432 KB Ok
28 Correct 102 ms 3356 KB Ok
29 Correct 248 ms 6836 KB Ok
30 Correct 11 ms 860 KB Ok
31 Correct 1 ms 348 KB Ok
32 Correct 7 ms 564 KB Ok
33 Correct 23 ms 1248 KB Ok
34 Correct 1 ms 344 KB Ok
35 Correct 0 ms 348 KB Ok
36 Correct 1 ms 348 KB Ok
37 Correct 0 ms 348 KB Ok
38 Correct 166 ms 3296 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 3252 KB Ok
2 Correct 181 ms 6396 KB Ok
3 Correct 185 ms 6772 KB Ok
4 Correct 11 ms 856 KB Ok
5 Correct 1 ms 348 KB Ok
6 Correct 27 ms 1100 KB Ok
7 Correct 209 ms 6496 KB Ok
8 Correct 1 ms 344 KB Ok
9 Correct 0 ms 348 KB Ok
10 Correct 1 ms 348 KB Ok
11 Correct 42 ms 1892 KB Ok
12 Correct 107 ms 3400 KB Ok