Submission #951196

#	Time	Username	Problem	Language	Result	Execution time	Memory
951196		kilkuwu	Unscrambling a Messy Bug (IOI16_messy)	C++17	38 / 100	1 ms	548 KiB

messy

#include <bits/stdc++.h>

#ifndef LOCAL
#include "messy.h"
#else

#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <cstdlib>
#include <iostream>

void add_element(std::string x);
bool check_element(std::string x);
void compile_set();

std::vector<int> restore_permutation(int n, int w, int r);


namespace helper {

std::set<std::string> set_;
bool compiled = false;
int n;
std::vector<int> p;
int w;
int r;

int read_int() {
  int x;
  std::cin >> x;
  return x;
}

}


int get_p(int i) {
  using namespace helper;
  int ret = p[i];
  return ret;
}

int main() {
  using namespace helper;
  n = read_int();
  w = read_int();
  r = read_int();
  p = std::vector<int>(n);
  for (int i = 0; i < n; i++) {
    p[i] = read_int();
  }
  std::vector<int> answer = restore_permutation(n, w, r);

  if ((int) answer.size() != n) {
    printf("WA\n");
    return 0;
  }


  printf("%d", answer[0]);

  for (int i = 1; i < n; i++) {
    printf(" %d", answer[i]);
  }
  printf("\n");
  return 0;
}

void wa() {
  printf("WA\n");
  exit(0);
}

bool check(const std::string& x) {
  using namespace helper;
  if ((int)x.length() != n) {
    return false;
  }
  for (int i = 0; i < n; i++) {
    if (x[i] != '0' && x[i] != '1') {
      return false;
    }
  }
  return true;
}

void add_element(std::string x) {
  using namespace helper;
  if (--w < 0 || compiled || !check(x)) {
    wa();
  }
  set_.insert(x);
}

bool check_element(std::string x) {
  using namespace helper;
  if (--r < 0 || !compiled || !check(x)) {
    wa();
  }
  return set_.count(x);
}

void compile_set() {
  using namespace helper;
  if (compiled) {
    wa();
  }
  compiled = true;
  std::set<std::string> compiledSet;
  std::string compiledElement = std::string(n, ' ');
  for (std::set<std::string>::iterator it = set_.begin(); it != set_.end(); it++) {
    std::string s = *it;
    for (int i = 0; i < n; i++) {
      compiledElement[i] = s[get_p(i)];
    }
    compiledSet.insert(compiledElement);
  }
  set_ = compiledSet;
}
#endif

std::vector<int> restore_permutation(int n, int w, int r) {
  std::vector<int> p(n);

  std::string s(n, '0');
  for (int i = 0; i + 1 < n; i++) {
    p.back() ^= n - i - 1;
    s[i] = '1';
    add_element(s);
  }

  compile_set();

  std::vector<int> found(n);

  s = std::string(n, '0');
  for (int i = 0; i + 1 < n; i++) {
    for (int j = 0; j < n; j++) {
      if (found[j] == 0) {
        s[j] = '1';
        int res = check_element(s);
        if (res) {
          p[i] = j;
          found[j] = 1;
          p.back() ^= j;
          break;
        }
        s[j] = '0';
      }
    }
  }

  std::vector<int> res(n);
  for (int i = 0; i < n; i++) {
    res[p[i]] = i;
  }

  return res;
}

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