Submission #800987

#	Time	Username	Problem	Language	Result	Execution time	Memory
800987		PixelCat	Unscrambling a Messy Bug (IOI16_messy)	C++14	70 / 100	2 ms	468 KiB

messy

#include "messy.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

// chars = "01" or "10"
string make_str(int n, vector<int> v, string chars) {
    string s;
    For(i, 1, n) s.push_back(chars[0]);
    for(auto &i:v) s[i] = chars[1];
    return s;
}

void prepare(int n, int lg) {
    vector<int> v;
    For(i, 1, lg) {
        v.eb(i - 1);
        add_element(make_str(n, v, "10"));
    }
    For(i, 0, lg - 1) {
        v.clear();
        v.eb(i);
        For(j, lg, n - 1) if(j & (1 << i)) {
            v.eb(j);
            add_element(make_str(n, v, "01"));
            v.pop_back();
        }
    }
}

vector<int> solve(int n, int lg) {
    vector<int> res(n, -1);
    vector<int> v;
    vector<int> ban(n, 0);
    For(i, 0, lg - 1) {
        For(j, 0, n - 1) if(!ban[j]) {
            v.eb(j);
            if(check_element(make_str(n, v, "10"))) {
                res[j] = i;
                ban[j] = 1;
                break;
            }
            v.pop_back();
        }
    }
    For(i, 0, n - 1) if(!ban[i]) res[i] = 0;
    vector<int> v2;
    For(i, 0, lg - 1) {
        v2.clear();
        v2.eb(v[i]);
        For(j, 0, n - 1) if(!ban[j]) {
            v2.eb(j);
            if(check_element(make_str(n, v2, "01"))) {
                res[j] |= (1 << i);
            }
            v2.pop_back();
        }
    }
    return res;
}

vector<int32_t> restore_permutation(int32_t n, int32_t w, int32_t r) {
    assert(max(w, r) > 0);
    int lg = __lg(n);
    prepare(n, lg);
    compile_set();
    vector<int> res = solve(n, lg);
    return vector<int32_t>(all(res));
}

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