Submission #288554

#	Time	Username	Problem	Language	Result	Execution time	Memory
288554		Tangent	Unscrambling a Messy Bug (IOI16_messy)	C++17	20 / 100	1 ms	384 KiB

messy

#include <bits/stdc++.h>

#include "messy.h"

using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// find_by_order(), order_of_key()

typedef long long ll;
typedef long double dd;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<dd, dd> pdd;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<dd> vdd;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pdd> vpdd;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vdd> vvdd;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
typedef vector<vpdd> vvpdd;
typedef vector<bool> vb;

const int inf = 1 << 30;

#define rep(i, n) for (ll i = 0; i < n; i++)
#define ffor(i, a, b) for(ll i = a; i < b; i++)
#define forin(x, a) for (auto &x: a)
#define all(x) x.begin(), x.end()

#ifdef TEST
#define dbg(x) cout << #x << ": " << x << '\n';
#define dbgc(x) cout << #x << ":"; forin(a, x) { cout << " " << a; } cout << endl;
#define tassert(x) assert(x);
#else
#define dbg(x)
#define dbgc(x)
#define tassert(x)
#endif

string con1(int a, int b) {
  string res(8, '0');
  res[a] = '1';
  res[b] = '1';
  return res;
}

std::vector<int> restore_permutation(int n, int w, int r) {
  if (n == 8) {
    add_element("01000000");
    add_element("00010000");
    add_element("00000100");
    add_element("00000001");
    add_element("11011111");
    add_element("11101111");
    add_element("11111101");
    add_element("11111110");
    add_element("00001100");
    add_element("00001010");
    add_element("00001001");
    add_element("00000110");
    add_element("00000101");
    add_element("00000011");
    compile_set();
    string ones(8, '1'), zeros(8, '0');
    vii g[4];
    rep(i, 8) {
      int curr = 0;
      zeros[i] = '1';
      ones[i] = '0';
      if (check_element(zeros)) {
        curr |= 1;
      }
      if (check_element(ones)) {
        curr |= 2;
      }
      zeros[i] = '0';
      ones[i] = '1';

      g[curr].emplace_back(i);
    }
    vii res(8, -1);
    if (check_element(con1(g[0][0], g[1][0]))) {
      res[g[0][0]] = 4;
      res[g[0][1]] = 0;
      res[g[1][0]] = 5;
      res[g[1][1]] = 1;
    } else if (check_element(con1(g[0][1], g[1][0]))) {
      res[g[0][0]] = 0;
      res[g[0][1]] = 4;
      res[g[1][0]] = 5;
      res[g[1][1]] = 1;
    } else if (check_element(con1(g[0][0], g[1][1]))) {
      res[g[0][0]] = 4;
      res[g[0][1]] = 0;
      res[g[1][0]] = 1;
      res[g[1][1]] = 5;
    } else {
      res[g[0][0]] = 0;
      res[g[0][1]] = 4;
      res[g[1][0]] = 1;
      res[g[1][1]] = 5;
    }

    if (check_element(con1(g[2][0], g[3][0]))) {
      res[g[2][0]] = 6;
      res[g[2][1]] = 2;
      res[g[3][0]] = 7;
      res[g[3][1]] = 3;
    } else if (check_element(con1(g[2][1], g[3][0]))) {
      res[g[2][0]] = 2;
      res[g[2][1]] = 6;
      res[g[3][0]] = 7;
      res[g[3][1]] = 3;
    } else if (check_element(con1(g[2][0], g[3][1]))) {
      res[g[2][0]] = 6;
      res[g[2][1]] = 2;
      res[g[3][0]] = 3;
      res[g[3][1]] = 7;
    } else {
      res[g[2][0]] = 2;
      res[g[2][1]] = 6;
      res[g[3][0]] = 3;
      res[g[3][1]] = 7;
    }
    return res;
  }
  add_element("0");
  compile_set();
  check_element("0");
  return std::vector<int>();
}

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