oj.uz

Submission #330747

# Submission time Handle Problem Language Result Execution time Memory
330747 2020-11-26T13:01:05 Z AlexLuchianov "The Lyuboyn" code (IZhO19_lyuboyn) C++14
100 / 100
 330 ms 6748 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 18;

std::vector<int> gray(int n) {
  std::vector<int> v;
  if(n == 1) {
    v.push_back(0);
    v.push_back(1);
    return v;
  } else {
    std::vector<int> v2 = gray(n - 1);
    std::vector<int> v3 = v2;
    std::reverse(v3.begin(), v3.end());
    for(int i = 0; i < v3.size(); i++)
      v2.push_back(v3[i] + (1 << (n - 1)));
    return v2;
  }
}

class IndependentSet{
private:
  std::vector<std::pair<int,int>> v;
public:
  IndependentSet() {

  }
  int reduce(int number) {
    
    for(int i = 0; i < v.size(); i++)
      if((1 << v[i].first) & number)
        number ^= v[i].second;
    return number;
  }
  void add_set(int number) {
    number = reduce(number);
    for(int i = 0; i < nmax; i++)
      if((1 << i) & number) {
        v.push_back({i, number});
        return ;
      }
  }
};

void print(int number, int n) {
  for(int i = n - 1; 0 <= i; i--)
    std::cout << (0 < ((1 << i) & number));
  std::cout << '\n';
}
int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  int n, k, t;
  std::cin >> n >> k >> t;
  IndependentSet myset;
  std::vector<int> target;
  for(int i = 0; i < (1 << n); i++)
    if(k == __builtin_popcount(i) && 0 < myset.reduce(i)) {
      target.push_back(i);
      myset.add_set(i);
    }
  
  std::vector<int> aux = gray(n);
  
  if(target.size() == n) {
    std::cout << (1 << n) << '\n';
    int start = 0;
    for(int i = n - 1; 0 <= i; i--) {
      char ch;
      std::cin >> ch;
      ch -= '0';
      start |= (ch<<i);
    }
    print(start, n);
    for(int i = 1; i < (1 << n); i++) {
      for(int j = 0; j < n; j++) 
        if((aux[i] ^ aux[i - 1]) == (1 << j))
          start ^= target[j];
      print(start, n);
    }
  } else
    std::cout << -1;
  return 0;
}

Compilation message

lyuboyn.cpp: In function 'std::vector<int> gray(int)':
lyuboyn.cpp:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i = 0; i < v3.size(); i++)
      |                    ~~^~~~~~~~~~~
lyuboyn.cpp: In member function 'int IndependentSet::reduce(int)':
lyuboyn.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int i = 0; i < v.size(); i++)
      |                    ~~^~~~~~~~~~
lyuboyn.cpp: In function 'int main()':
lyuboyn.cpp:74:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |   if(target.size() == n) {
      |      ~~~~~~~~~~~~~~^~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 4 ms 2040 KB Ok
3 Correct 4 ms 1260 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 384 KB Ok
7 Correct 1 ms 364 KB Ok
8 Correct 4 ms 1260 KB Ok

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 6492 KB Ok
2 Correct 174 ms 3428 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Ok
2 Correct 9 ms 492 KB Ok
3 Correct 149 ms 3300 KB Ok
4 Correct 79 ms 1900 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 2 ms 364 KB Ok
7 Correct 33 ms 1132 KB Ok
8 Correct 1 ms 364 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 6492 KB Ok
2 Correct 330 ms 6492 KB Ok
3 Correct 317 ms 6580 KB Ok
4 Correct 161 ms 3300 KB Ok
5 Correct 169 ms 3300 KB Ok
6 Correct 70 ms 1900 KB Ok
7 Correct 73 ms 2028 KB Ok
8 Correct 33 ms 1260 KB Ok
9 Correct 43 ms 1132 KB Ok
10 Correct 16 ms 748 KB Ok
11 Correct 1 ms 364 KB Ok
12 Correct 1 ms 364 KB Ok
13 Correct 1 ms 364 KB Ok

Subtask #7
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 6492 KB Ok
2 Correct 174 ms 3428 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 1 ms 364 KB Ok
7 Correct 9 ms 492 KB Ok
8 Correct 149 ms 3300 KB Ok
9 Correct 79 ms 1900 KB Ok
10 Correct 1 ms 364 KB Ok
11 Correct 2 ms 364 KB Ok
12 Correct 33 ms 1132 KB Ok
13 Correct 1 ms 364 KB Ok
14 Correct 318 ms 6492 KB Ok
15 Correct 330 ms 6492 KB Ok
16 Correct 317 ms 6580 KB Ok
17 Correct 161 ms 3300 KB Ok
18 Correct 169 ms 3300 KB Ok
19 Correct 70 ms 1900 KB Ok
20 Correct 73 ms 2028 KB Ok
21 Correct 33 ms 1260 KB Ok
22 Correct 43 ms 1132 KB Ok
23 Correct 16 ms 748 KB Ok
24 Correct 1 ms 364 KB Ok
25 Correct 1 ms 364 KB Ok
26 Correct 1 ms 364 KB Ok
27 Correct 324 ms 6492 KB Ok
28 Correct 151 ms 3428 KB Ok
29 Correct 312 ms 6492 KB Ok
30 Correct 16 ms 748 KB Ok
31 Correct 1 ms 364 KB Ok
32 Correct 8 ms 492 KB Ok
33 Correct 34 ms 1132 KB Ok
34 Correct 1 ms 364 KB Ok
35 Correct 1 ms 364 KB Ok
36 Correct 1 ms 364 KB Ok
37 Correct 1 ms 364 KB Ok
38 Correct 149 ms 3300 KB Ok

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 3300 KB Ok
2 Correct 323 ms 6748 KB Ok
3 Correct 313 ms 6492 KB Ok
4 Correct 16 ms 748 KB Ok
5 Correct 1 ms 364 KB Ok
6 Correct 33 ms 1132 KB Ok
7 Correct 313 ms 6620 KB Ok
8 Correct 1 ms 364 KB Ok
9 Correct 1 ms 364 KB Ok
10 Correct 2 ms 364 KB Ok
11 Correct 73 ms 1900 KB Ok
12 Correct 149 ms 3300 KB Ok