Submission #288629

#	Time	Username	Problem	Language	Result	Execution time	Memory
288629		Tangent	Unscrambling a Messy Bug (IOI16_messy)	C++17	49 / 100	1 ms	512 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 (int 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;
}

string cones(vii a) {
  string res(32, '1');
  forin(x, a) {
    res[x] = '0';
  }
  return res;
}

string czeros(vii a) {
  string res(32, '0');
  forin(x, a) {
    res[x] = '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;
  }
  else if (n == 32) {
    string ones(32, '1'), zeros(32, '0');

    rep(i, n) {
      if (i & 1) {
        add_element(czeros({i}));
      }
      if (i & 2) {
        add_element(cones({i}));
      }
    }
    rep(i, 4) {
      add_element(czeros({4 | i, 12 | i}));
      add_element(czeros({4 | i, 20 | i}));
      add_element(czeros({4 | i, 28 | i}));
      add_element(czeros({12 | i, 20 | i}));
      add_element(czeros({12 | i, 28 | i}));
      add_element(czeros({20 | i, 28 | i}));
    }
    rep(i, 4) {
      add_element(cones({8 | i, 12 | i}));
      add_element(cones({8 | i, 24 | i}));
      add_element(cones({8 | i, 28 | i}));
      add_element(cones({12 | i, 24 | i}));
      add_element(cones({12 | i, 28 | i}));
      add_element(cones({24 | i, 28 | i}));
    }
    rep(i, 4) {
      add_element(czeros({16 | i, 20 | i, 24 | i, 28 | i}));
    }
    compile_set();
    vii inv(32, -1);
    int rem[2][2] = {{16, 16}, {16, 16}};
    vii g[4];
    rep(i, 32) {
      int curr = 0;
      rep(j, 2) {
        if (!rem[j][0]) {
          curr |= (j + 1);
        } else if (rem[j][1]) {
          if (j) {
            if (check_element(cones({i}))) {
              curr |= (j + 1);
              rem[j][1]--;
            } else {
              rem[j][0]--;
            }
          } else {
            if (check_element(czeros({i}))) {
              curr |= (j + 1);
              rem[j][1]--;
            } else {
              rem[j][0]--;
            }
          }
        }
      }
      g[curr].emplace_back(i);
      inv[i] = curr;
    }
    rep(i, 4) {
      auto &cg = g[i];
      int j = 0, k = 1;
      bool ff = false;
      while (j < 7) {
        if (j == 6) {
          tassert(ff);
          inv[cg[6]] |= 4;
          inv[cg[7]] |= 4;
          break;
        }
        if (!ff && j == 4) {
          inv[cg[4]] |= 4;
          inv[cg[5]] |= 4;
          inv[cg[6]] |= 4;
          inv[cg[7]] |= 4;
          break;
        }
        if (check_element(czeros({cg[j], cg[k]}))) {
          if (ff) {
            inv[cg[j]] |= 4;
            inv[cg[k]] |= 4;
            break;
          } else {
            ff = true;
            inv[cg[j]] |= 4;
            inv[cg[k]] |= 4;
            j = k + 1;
            k = j + 1;
          }
        } else if (k == 7 || (!ff && k == 5)){
          j++;
          k = j + 1;
        } else {
          k++;
        }
      }
    }
    rep(i, 4) {
      auto &cg = g[i];
      int j = 0, k = 1;
      bool ff = false;
      while (j < 7) {
        if (j == 6) {
          tassert(ff);
          inv[cg[6]] |= 8;
          inv[cg[7]] |= 8;
          break;
        }
        if (!ff && j == 4) {
          inv[cg[4]] |= 8;
          inv[cg[5]] |= 8;
          inv[cg[6]] |= 8;
          inv[cg[7]] |= 8;
          break;
        }
        if (check_element(cones({cg[j], cg[k]}))) {
          if (ff) {
            inv[cg[j]] |= 8;
            inv[cg[k]] |= 8;
            break;
          } else {
            ff = true;
            inv[cg[j]] |= 8;
            inv[cg[k]] |= 8;
            j = k + 1;
            k = j + 1;
          }
        } else if (k == 7 || (!ff && k == 5)){
          j++;
          k = j + 1;
        } else {
          k++;
        }
      }
    }
    rep(i, 4) {
      vii g2[4];
      forin(x, g[i]) {
        g2[inv[x] >> 2].emplace_back(x);
      }
      bool found = false;
      rep(j, 15) {
        vii curr;
        int k = j;
        rep(l, 4) {
          curr.emplace_back(g2[l][k & 1]);
          k >>= 1;
        }
        if (check_element(czeros(curr))) {
          found = true;
          forin(x, curr) {
            inv[x] |= 16;
          }
          break;
        }
      }
      if (!found) {
        rep(j, 4) {
          inv[g2[j][1]] |= 16;
        }
      }
    }
    vii res(32);
    rep(i, 32) {
      res[inv[i]] = i;
    }
    return inv;
  }
  add_element("0");
  compile_set();
  check_element("0");
  return std::vector<int>();
}

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