Submission #393473

#	Time	Username	Problem	Language	Result	Execution time	Memory
393473		usachevd0	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	3 ms	588 KiB

messy

#include <bits/stdc++.h>
#ifndef DEBUG
  #include "messy.h"
#endif

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
  return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
  return y > x ? (x = y, true) : false;
}
void debug_out() {
  cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
  cerr << ' ' << A;
  debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
  for (int i = 0; i < n; ++i) cerr << a[i];
  cerr << endl;
}
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
  for (auto& x : v) {
    stream << x << ' ';
  }
  return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
  return stream << p.first << ' ' << p.second;
}

#ifdef DEBUG
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
  #define debug(...) 1337
  #define mdebug(a, n) 1337
#endif


#ifdef DEBUG
  int n, W, R;
  vector<int> p;
  set<string> S;

  void add_element(string s) {
    assert(--W >= 0);
    string t(n, '?');
    for (int i = 0; i < n; ++i) {
      t[i] = s[p[i]];
    }
//    debug(s);
//    debug(t);
    S.insert(t);
  }
  void compile_set() {
  }
  bool check_element(string s) {
    assert(--R >= 0);
    return S.count(s);
  }
#endif

char inv(char c) {
  return '1' - c + '0';
}

vector<int> restore_permutation(int n, int W, int R) {
  int k = 0;
  while ((1 << k) < n) ++k;

  string M(n, '0');
  for (int j = 0; j < k - 1; ++j) {
    string newM(all(M));
    for (int i = 0; i < n; ++i) {
      if ((i >> j) & 1) {
        string q(all(M));
        q[i] = inv(q[i]);
        add_element(q);
        newM[i] = '1';
      }
    }
    swap(M, newM);
//    debug(M);
  }
  for (int i = n / 2; i < n; ++i) {
    string q(n, '1');
    q[i] = '0';
    add_element(q);
  }
  compile_set();

  vector<vector<char>> A(k, vector<char>(n, false));
  M = string(n, '0');
  for (int j = 0; j < k - 1; ++j) {
    string newM(all(M));
    for (int i = 0; i < n; ++i) {
      string q(all(M));
      q[i] = inv(q[i]);
      if (check_element(q)) {
        A[j][i] = true;
        newM[i] = '1';
      }
    }
    swap(M, newM);
  }
  for (int i = 0; i < n; ++i) {
    string q(n, '1');
    q[i] = '0';
    if (check_element(q)) {
      A[k - 1][i] = true;
    }
  }

  vector<int> p(n);
  for (int x = 0; x < n; ++x) {
    vector<char> mask(n, true);
    for (int j = 0; j < k; ++j) {
      for (int i = 0; i < n; ++i) {
        mask[i] &= A[j][i] == ((x >> j) & 1);
      }
    }
    assert(count(all(mask), true) == 1);
    int i = find(all(mask), true) - mask.begin();
    p[i] = x;
  }
  return p;
}

#ifdef DEBUG
int32_t main() {
#ifdef DEBUG
  freopen("in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);

  mt19937 rng(228);
  for (int itr = 1; ; ++itr) {
    n = 8;
    int k = 0;
    while ((1 << k) < n) ++k;
    W = k * n;
    R = k * n;
    p.resize(n);
    iota(all(p), 0);
    shuffle(all(p), rng);
    //debug(p);
    S.clear();
    if (restore_permutation(n, W, R) != p) {
      cerr << "BAD";
      exit(0);
    }
    debug(itr);
  }

  return 0;
}
#endif

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