Submission #951343

#	Time	Username	Problem	Language	Result	Execution time	Memory
951343		kilkuwu	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	2 ms	856 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

#ifdef LOCAL
#include "template\debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

std::vector<int> restore_permutation(int n, int w, int r) {
  std::string s(n, '1');
  
  for (int num_block = 1; num_block < n; num_block *= 2) {
    int block_size = n / num_block;
    for (int b = 0; b < num_block; b++) {
      int st = block_size * b;
      for (int i = st; i < st + block_size; i++) {
        s[i] = '0';
        // we will add into our element
      }
      for (int i = st; i < st + block_size / 2; i++) {
        s[i] = '1';
        add_element(s);
        s[i] = '0';
      }
      for (int i = st; i < st + block_size; i++) {
        s[i] = '1';
        // we will add into our element
      }
    }
  }


  compile_set();

  std::vector<int> p(n);
  std::iota(p.begin(), p.end(), 0);
  std::vector<int> marked(n);

  for (int num_block = 1; num_block < n; num_block *= 2) {
    int block_size = n / num_block;

    for (int b = 0; b < num_block; b++) {
      int st = block_size * b;
      for (int i = st; i < st + block_size; i++) {
        s[p[i]] = '0';
      }
      for (int i = st; i < st + block_size; i++) {
        s[p[i]] = '1';
        if (check_element(s)) {
          marked[i] = 1;
        }
        s[p[i]] = '0';
      }

      for (int i = st, j = st; i < st + block_size; i++) {
        if (marked[i]) {
          std::swap(p[i], p[j]);
          j++;
          marked[i] = 0;
        } 
      }

      for (int i = st; i < st + block_size; i++) {
        s[p[i]] = '1';
      }
    }
  }

  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: 11 / 11
• Subtask 4: 21 / 21
• Subtask 5: 30 / 30