Submission #960083

#	Time	Username	Problem	Language	Result	Execution time	Memory
960083		LucaLucaM	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	2 ms	604 KiB

messy

#include <vector>
#include <set>
#include <iostream>
#include <fstream>

#include "messy.h"

bool exista(std::string s) {
  return check_element(s);
}

void change (char &c) {
  c = (c == '0'? '1' : '0');
}

std::set<int> where[8];

std::vector<int> restore_permutation(int n, int w, int r) {
  int logN = std::__lg(n);
  std::vector<int> made;

  for(int i = 0; i < logN; i++) {
    std::string s(n, '0');
    for (const auto &index : made) {
      s[index] = '1';
    }

    if(i == logN - 1) {
      s = std::string(n, '1');
    }

    for(int j = 0; j < n; j++) {
      if((j >> i) & 1) {
        change(s[j]);
        add_element(s);
        change(s[j]);
        made.push_back(j);
      }
    }
  }

  compile_set();
  made.clear();

  for(int i = 0; i < logN; i++) {
    std::string s(n, '0');
    for (const auto &index : made) {
      s[index] = '1';
    }

    if(i == logN - 1) {
      s = std::string(n, '1');
    }

    for(int j = 0; j < n; j++) {
      change(s[j]);
      if(exista(s)) {
        where[i].insert(j);
        made.push_back(j);
      }
      change(s[j]);
    }
  }

  std::vector<int> p(n, 0);
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < logN; j++)
      if(where[j].count(i))
        p[i] |= (1 << j);
  }

  return p;
}

/**

4 16 16
2 1 3 0

**/

• Subtask 1: 20 / 20
• Subtask 2: 18 / 18
• Subtask 3: 11 / 11
• Subtask 4: 21 / 21
• Subtask 5: 30 / 30