Submission #562761

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

messy

#include "messy.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

vi ans;
bitset<300> inside;

void Solve(vi ind1, vi ind2) {
    int sz = ind1.size();
    if (sz == 1) {
        ans[ind2[0]] = ind1[0];
        return;
    }
    int mask = 0;
    for (int x : ind2) mask += 1 << x;
    for (int i = 1; i < (1 << 8); i++) {
        if (__builtin_popcount(i) != sz / 2 || !inside[i]) continue;
        if ((i & mask) != i) continue;
        vi l1(ind1.begin(), ind1.begin() + sz / 2);
        vi r1(ind1.begin() + sz / 2, ind1.end());
        vi l2, r2;
        for (int x : ind2) {
            if ((i >> x) & 1) l2.push_back(x);
            else r2.push_back(x);
        }
        Solve(l1, l2), Solve(r1, r2);
        break;
    }
}

inline string Convert(int x) {
    string s(8, '0');
    for (int i = 0; i < 8; i++) {
        s[i] = (x >> i) & 1 ? '1' : '0';
    }
    return s;
}

std::vector<int> restore_permutation(int n, int w, int r) {
    add_element("11110000");
    add_element("11000000");
    add_element("00001100");
    add_element("10000000");
    add_element("00100000");
    add_element("00001000");
    add_element("00000010");
    compile_set();
    for (int i = 0; i < (1 << 8); i++) {
        string s = Convert(i);
        inside[i] = check_element(s);
    }
    ans.resize(8);
    vi v(8);
    iota(all(v), 0);
    Solve(v, v);
    return ans;
}
//8 256 256
//2 0 4 7 5 6 1 3

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