Submission #330747

#	Time	Username	Problem	Language	Result	Execution time	Memory
330747		AlexLuchianov	"The Lyuboyn" code (IZhO19_lyuboyn)	C++14	100 / 100	330 ms	6748 KiB

lyuboyn

#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 (stderr)

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
• Subtask 2: 5 / 5
• Subtask 3: 3 / 3
• Subtask 4: 11 / 11
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 31 / 31
• Subtask 8: 17 / 17