Submission #1088938

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

messy

#include <vector>
#include <string>
#include <algorithm>
#include <cassert>
#include <numeric>
#include "messy.h"
 
using namespace std;
 
int N;
 
void _add_element(vector<int> x) {
  string S(N, '0');
  
  for(int i : x) S[i] = '1';
  
  add_element(S);
}
 
bool _check_element(vector<int> x) {
  string S(N, '0');
  
  for(int i : x) S[i] = '1';
  
  return check_element(S);
}
 
void add(int s, int e, vector<int> tmp) {
  if (s == e) {
    return;
  }
  
  int m = (s + e) >> 1;
  
  for(int i = s; i <= m; i++) {
    auto v = tmp;
    v.push_back(i);
    _add_element(v);
  }
  
  vector<int> v1, v2;
  
  for(int i = s; i <= m; i++) v2.push_back(i);
  for(int i = m+1; i <= e; i++) v1.push_back(i);
  
  add(s, m, v1);
  add(m+1, e, v2);
}
 
vector<int> check(int s, int e, vector<int> cand, vector<int> tmp) {
  assert(int(cand.size()) == e - s + 1);
  
  if(s == e) return cand;
  
  vector<vector<int>> ok(2);
  
  for(int i : cand) {
    auto v = tmp;
    v.push_back(i);
    
    ok[!_check_element(v)].push_back(i);
  }
  
  int m = (s + e) >> 1;
  auto l = check(s, m, ok[0], ok[1]);
  auto r = check(m+1, e, ok[1], ok[0]);
  
  for(int i : r) l.push_back(i);
  return l;
}
 
vector<int> restore_permutation(int n, int w, int r) {
  N = n;
  
  add(0, N-1, vector<int>());
  compile_set();
  vector<int> a(N);
  iota(a.begin(), a.end(), 0);
  auto x = check(0, N-1, a, vector<int>());

  vector<int> p(N);
  for(int i = 0; i < N; i++) p[x[i]] = i;
  return p;
}

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