oj.uz

Submission #895634

# Submission time Handle Problem Language Result Execution time Memory
895634 2023-12-30T12:19:59 Z mychecksedad "The Lyuboyn" code (IZhO19_lyuboyn) C++17
69 / 100
 276 ms 7020 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 < 100; ++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 4 ms 348 KB Ok
2 Correct 148 ms 348 KB Ok
3 Correct 235 ms 660 KB Ok
4 Correct 0 ms 344 KB Ok
5 Correct 1 ms 460 KB Ok
6 Correct 10 ms 344 KB Ok
7 Correct 17 ms 348 KB Ok
8 Correct 276 ms 348 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 6480 KB Ok
2 Correct 86 ms 3420 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 344 KB Ok
2 Correct 5 ms 604 KB Ok
3 Correct 92 ms 3400 KB Ok
4 Correct 41 ms 1744 KB Ok
5 Correct 1 ms 348 KB Ok
6 Correct 2 ms 484 KB Ok
7 Correct 20 ms 1232 KB Ok
8 Correct 1 ms 348 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 7020 KB Ok
2 Correct 200 ms 6460 KB Ok
3 Correct 196 ms 6608 KB Ok
4 Correct 100 ms 3604 KB Ok
5 Correct 99 ms 3420 KB Ok
6 Correct 42 ms 1988 KB Ok
7 Correct 41 ms 1720 KB Ok
8 Correct 21 ms 1372 KB Ok
9 Correct 21 ms 1364 KB Ok
10 Correct 10 ms 856 KB Ok
11 Correct 1 ms 348 KB Ok
12 Correct 1 ms 348 KB Ok
13 Correct 0 ms 348 KB Ok

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 6480 KB Ok
2 Correct 86 ms 3420 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 344 KB Ok
7 Correct 5 ms 604 KB Ok
8 Correct 92 ms 3400 KB Ok
9 Correct 41 ms 1744 KB Ok
10 Correct 1 ms 348 KB Ok
11 Correct 2 ms 484 KB Ok
12 Correct 20 ms 1232 KB Ok
13 Correct 1 ms 348 KB Ok
14 Correct 211 ms 7020 KB Ok
15 Correct 200 ms 6460 KB Ok
16 Correct 196 ms 6608 KB Ok
17 Correct 100 ms 3604 KB Ok
18 Correct 99 ms 3420 KB Ok
19 Correct 42 ms 1988 KB Ok
20 Correct 41 ms 1720 KB Ok
21 Correct 21 ms 1372 KB Ok
22 Correct 21 ms 1364 KB Ok
23 Correct 10 ms 856 KB Ok
24 Correct 1 ms 348 KB Ok
25 Correct 1 ms 348 KB Ok
26 Correct 0 ms 348 KB Ok
27 Correct 186 ms 6392 KB Ok
28 Correct 138 ms 3304 KB Ok
29 Correct 194 ms 6836 KB Ok
30 Correct 11 ms 856 KB Ok
31 Correct 1 ms 348 KB Ok
32 Correct 5 ms 612 KB Ok
33 Correct 22 ms 1248 KB Ok
34 Correct 1 ms 344 KB Ok
35 Correct 1 ms 344 KB Ok
36 Correct 1 ms 348 KB Ok
37 Correct 0 ms 348 KB Ok
38 Incorrect 78 ms 348 KB Output -1 while solution exists
39 Halted 0 ms 0 KB -

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 3400 KB Ok
2 Correct 188 ms 6600 KB Ok
3 Correct 197 ms 6840 KB Ok
4 Correct 10 ms 856 KB Ok
5 Correct 1 ms 348 KB Ok
6 Correct 29 ms 1304 KB Ok
7 Correct 201 ms 6712 KB Ok
8 Correct 1 ms 348 KB Ok
9 Correct 0 ms 348 KB Ok
10 Correct 1 ms 348 KB Ok
11 Correct 47 ms 1900 KB Ok
12 Correct 94 ms 3324 KB Ok