oj.uz

Submission #538634

# Submission time Handle Problem Language Result Execution time Memory
538634 2022-03-17T09:49:31 Z cig32 "The Lyuboyn" code (IZhO19_lyuboyn) C++17
100 / 100
 153 ms 9080 KB 
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
#define ll __int128
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
ll read() { // read int128
  int x; cin >> x; return (ll)x;
}
long long bm(long long b, long long p) {
  if(p==0) return 1 % MOD;
  long long r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
long long inv(long long b) { 
  return bm(b, MOD-2);
}
long long f[MAXN];
long long nCr(int n, int r) { 
  long long ans = f[n]; ans *= inv(f[r]); ans %= MOD;
  ans *= inv(f[n-r]); ans %= MOD; return ans;
}
void precomp() { 
  for(int i=0; i<MAXN; i++) f[i] = (i == 0 ? 1 % MOD : (f[i-1] * i) % MOD);
}
void solve(int tc) {
  int n, k, t;
  cin >> n >> k >> t;
  string s;
  cin >> s;
  vector<int> ans;
  int xorsum = 0;
  ans.push_back(0);
  vector<int> tog;
  int cur = (1<<k) - 1;
  for(int i=1; i<=n; i++) {
    tog.push_back(cur);
    if(cur >= (1 << (n-1))) {
      cur -= (1 << (n-1));
      cur <<= 1;
      if(n % k == 0 && k > 1) cur += 2;
      else cur += 1;
    }
    else {
      cur <<= 1;
    }
  }
  for(int i=1; i<(1<<n); i++) {
    xorsum ^= tog[(int)log2(i & -i)];
    ans.push_back(xorsum);
    //cout << tog[(int)log2(i & -i)] << ' ';
    //if(i % 8 == 0) cout << '\n';
  }
  /*
  cout << '\n';
  cout << "tog[]: ";
  for(int i=0; i<n; i++) cout << tog[i] << ' ';
  cout << '\n';
  freopen("uwu.txt", "w", stdout);
  */
  if(k % 2 == 0) {
    cout << "-1\n";
    return;
  }
  cout << (1<<n) << '\n';
  int pos;
  int val = 0;
  for(int i=0; i<s.size(); i++) {
    val *= 2;
    val += (s[i] == '1');
  }
  for(int i=0; i<ans.size(); i++) {
    if(ans[i] == val) pos = i;
  }
  for(int i=pos; i<pos+ans.size(); i++) {
    for(int j=n-1; j>=0; j--) {
      if(ans[i % (1<<n)] & (1<<j)) cout << "1";
      else cout << "0";
    }
    cout << '\n';
  }
}
int32_t main(){
  precomp();
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
} 
/*

7 28 7 14 7 56 7 14 7 28 7 14 7 49 
6 3 0 000000

n = 6, k = 3
7 14 7 28 7 14 7 56 
7 14 7 28 7 14 7 49 
7 14 7 28 7 14 7 56 
7 14 7 28 7 14 7 35 
7 14 7 28 7 14 7 56 
7 14 7 28 7 14 7 49 
7 14 7 28 7 14 7 56 
7 14 7 28 7 14 7 
tog[]: 7 14 28 56 49 35 

n = 7, k = 3
7 14 7 28 7 14 7 56 
7 14 7 28 7 14 7 112 
7 14 7 28 7 14 7 56 
7 14 7 28 7 14 7 97 
7 14 7 28 7 14 7 56 
7 14 7 28 7 14 7 112 
7 14 7 28 7 14 7 56 
7 14 7 28 7 14 7 67 
7 14 7 28 7 14 7 56 
7 14 7 28 7 14 7 112 
7 14 7 28 7 14 7 56 
7 14 7 28 7 14 7 97 
7 14 7 28 7 14 7 56 
7 14 7 28 7 14 7 112 
7 14 7 28 7 14 7 56 
7 14 7 28 7 14 7 
tog[]: 7 14 28 56 112 97 67 


0
7
12
11
6
1
10
13
3
4
15
8
5
2
9
14

7
12
1
15
8
3
14
0
7
12
1
15
8
3
14

7  (0111)
13 (1101)
11 (1011)
7  (0111)
14 (1110)
13 (1101)
14 (1110)
7  (0111)
14 (1110)
13 (1101)
11 (1011)
13 (1101)
7  (0111)
13 (1101)
14 (1110)
*/

Compilation message

lyuboyn.cpp: In function 'void solve(long long int)':
lyuboyn.cpp:73:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for(int i=0; i<s.size(); i++) {
      |                ~^~~~~~~~~
lyuboyn.cpp:77:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for(int i=0; i<ans.size(); i++) {
      |                ~^~~~~~~~~~~
lyuboyn.cpp:80:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
   80 |   for(int i=pos; i<pos+ans.size(); i++) {
      |                  ~^~~~~~~~~~~~~~~
lyuboyn.cpp:80:20: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |   for(int i=pos; i<pos+ans.size(); i++) {
      |                    ^~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1876 KB Ok

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1876 KB Ok

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2004 KB Ok
2 Correct 7 ms 4048 KB Ok
3 Correct 5 ms 3076 KB Ok
4 Correct 2 ms 1876 KB Ok
5 Correct 3 ms 1876 KB Ok
6 Correct 3 ms 1908 KB Ok
7 Correct 2 ms 2004 KB Ok
8 Correct 5 ms 3044 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 8972 KB Ok
2 Correct 70 ms 5304 KB Ok
3 Correct 3 ms 1824 KB Ok
4 Correct 3 ms 1876 KB Ok
5 Correct 4 ms 1876 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1876 KB Ok
2 Correct 6 ms 2064 KB Ok
3 Correct 67 ms 5336 KB Ok
4 Correct 32 ms 3584 KB Ok
5 Correct 3 ms 1876 KB Ok
6 Correct 4 ms 1876 KB Ok
7 Correct 19 ms 2784 KB Ok
8 Correct 3 ms 1884 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 9016 KB Ok
2 Correct 147 ms 9024 KB Ok
3 Correct 143 ms 9020 KB Ok
4 Correct 89 ms 5392 KB Ok
5 Correct 67 ms 5316 KB Ok
6 Correct 32 ms 3604 KB Ok
7 Correct 35 ms 3616 KB Ok
8 Correct 19 ms 2784 KB Ok
9 Correct 18 ms 2796 KB Ok
10 Correct 9 ms 2388 KB Ok
11 Correct 3 ms 1876 KB Ok
12 Correct 3 ms 1876 KB Ok
13 Correct 3 ms 1876 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 8972 KB Ok
2 Correct 70 ms 5304 KB Ok
3 Correct 3 ms 1824 KB Ok
4 Correct 3 ms 1876 KB Ok
5 Correct 4 ms 1876 KB Ok
6 Correct 3 ms 1876 KB Ok
7 Correct 6 ms 2064 KB Ok
8 Correct 67 ms 5336 KB Ok
9 Correct 32 ms 3584 KB Ok
10 Correct 3 ms 1876 KB Ok
11 Correct 4 ms 1876 KB Ok
12 Correct 19 ms 2784 KB Ok
13 Correct 3 ms 1884 KB Ok
14 Correct 139 ms 9016 KB Ok
15 Correct 147 ms 9024 KB Ok
16 Correct 143 ms 9020 KB Ok
17 Correct 89 ms 5392 KB Ok
18 Correct 67 ms 5316 KB Ok
19 Correct 32 ms 3604 KB Ok
20 Correct 35 ms 3616 KB Ok
21 Correct 19 ms 2784 KB Ok
22 Correct 18 ms 2796 KB Ok
23 Correct 9 ms 2388 KB Ok
24 Correct 3 ms 1876 KB Ok
25 Correct 3 ms 1876 KB Ok
26 Correct 3 ms 1876 KB Ok
27 Correct 153 ms 9016 KB Ok
28 Correct 74 ms 5400 KB Ok
29 Correct 143 ms 9044 KB Ok
30 Correct 10 ms 2364 KB Ok
31 Correct 3 ms 1876 KB Ok
32 Correct 7 ms 2132 KB Ok
33 Correct 19 ms 2756 KB Ok
34 Correct 3 ms 1876 KB Ok
35 Correct 3 ms 1884 KB Ok
36 Correct 3 ms 1884 KB Ok
37 Correct 2 ms 1876 KB Ok
38 Correct 71 ms 5304 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 5348 KB Ok
2 Correct 146 ms 9080 KB Ok
3 Correct 143 ms 9024 KB Ok
4 Correct 9 ms 2264 KB Ok
5 Correct 3 ms 1780 KB Ok
6 Correct 19 ms 2744 KB Ok
7 Correct 138 ms 8944 KB Ok
8 Correct 3 ms 1876 KB Ok
9 Correct 3 ms 1876 KB Ok
10 Correct 3 ms 1892 KB Ok
11 Correct 35 ms 3544 KB Ok
12 Correct 69 ms 5352 KB Ok