제출 #108050

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
108050		PeppaPig	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	8 ms	512 KiB

messy

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

using namespace std;

int n;
vector<int> ans;

string gen_base(int l, int r, int idx) {
    string s(n, '1');
    for(int i = l; i <= r; i++) s[i] = '0';
    s[idx] = '1';
    return s;
}

string gen_find(vector<int> &v, int idx) {
    string s(n, '1');
    for(int pos : v) s[pos] = '0';
    s[idx] = '1';
    return s;
}

void build(int l = 0, int r = n-1) {
    if(l == r) return;
    int mid = (l + r) >> 1;
    for(int i = l; i <= mid; i++) add_element(gen_base(l, r, i));
    build(l, mid), build(mid+1, r);
}

void restore(vector<int> &v, int l = 0, int r = n-1) {
    if(l == r) return void(ans[v[0]] = l);
    vector<int> L, R;
    for(int pos : v) {
        if(check_element(gen_find(v, pos))) L.emplace_back(pos);
        else R.emplace_back(pos);
    }
    int mid = (l + r) >> 1;
    restore(L, l, mid), restore(R, mid+1, r);
}

vector<int> restore_permutation(int _n, int w, int r) {
    n = _n; 
    build(), compile_set();

    vector<int> v;
    for(int i = 0; i < n; i++) v.emplace_back(i);
    ans = vector<int>(n, 0);
    restore(v);

    return ans;
}

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