Submission #42795

#	Time	Username	Problem	Language	Result	Execution time	Memory
42795		funcsr	Unscrambling a Messy Bug (IOI16_messy)	C++14	70 / 100	4 ms	896 KiB

messy

#include "messy.h"
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
using namespace std;
#define rep(i, n) for (int i=0; i<(n); i++)
#define INF 1145141919

vector<int> restore_permutation(int n, int w, int r) {
  int x = n;
  int logn = 0;
  while (x>=2) logn++, x/=2;
  assert(logn < n-logn);
  string ones(n, '1');
  rep(i, logn) {
    ones[i] = '0';
    assert(w-- > 0);
    add_element(ones);
  }
  for (int i=logn; i<n; i++) {
    string zeros(n, '0');
    zeros[i] = '1';
    //add_element(zeros);
    rep(k, logn) if ((i>>k)&1) {
      zeros[k] = '1';
      assert(w-- > 0);
      add_element(zeros);
    }
  }
  vector<int> ret(n, -1), rev(n, -1);
  compile_set();
  string pat(n, '1');
  rep(i, logn) {
    int pos = -1;
    rep(p, n) if (pat[p] == '1') {
      pat[p] = '0';
      assert(r-- > 0);
      if (check_element(pat)) {
        pos = p;
        break;
      }
      pat[p] = '1';
    }
    assert(pos != -1 && rev[pos] == -1);
    ret[i] = pos;
    rev[pos] = i;
    pat[pos] = '0';
  }
  rep(i, n) if (rev[i] == -1) {
    string s(n, '0');
    s[i] = '1';
    //assert(check_element(s));
    int pos = 0;
    rep(j, logn) {
      s[ret[j]] = '1';
      assert(r-- > 0);
      if (check_element(s)) {
        pos |= 1<<j;
      }
      else s[ret[j]] = '0';
    }
    assert(ret[pos] == -1);
    ret[pos] = i;
    rev[i] = pos;
  }
  return rev;
}

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