oj.uz

Submission #330746

# Submission time Handle Problem Language Result Execution time Memory
330746 2020-11-26T12:59:14 Z AlexLuchianov "The Lyuboyn" code (IZhO19_lyuboyn) C++14
11 / 100
 381 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(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 512 KB Ok

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Fail, not exactly k bits are different: line = 0

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 492 KB Found solution while it does not exist
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 6564 KB Ok
2 Correct 155 ms 3300 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Fail, not exactly k bits are different: line = 0
2 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 381 ms 6748 KB Fail, not exactly k bits are different: line = 0
2 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 6564 KB Ok
2 Correct 155 ms 3300 KB Ok
3 Correct 1 ms 364 KB Ok
4 Correct 1 ms 364 KB Ok
5 Correct 1 ms 364 KB Ok
6 Incorrect 1 ms 364 KB Fail, not exactly k bits are different: line = 0
7 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 155 ms 3300 KB Fail, not exactly k bits are different: line = 0
2 Halted 0 ms 0 KB -