제출 #355606

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

messy

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

using namespace std;

void addStuff(int n, string pref, string suff) {
    if (n == 1) return;
    for (int i = n/2; i < n; i++) {
        string s;
        for (int j = 0; j < n; j++) {
            if (j == i) s += "1";
            else s += "0";
        }
        add_element(pref + s + suff);
    }
    string halfZeroes; for (int i = 0; i < n/2; i++) halfZeroes += "1";
    addStuff(n/2, pref+halfZeroes, suff);
    addStuff(n/2, pref, halfZeroes+suff);
}

void checkStuff(vector<int> &perm, int n, vector<int> indices, int lo, int hi) {
    if (indices.size() == 1) {
        perm[indices[0]] = lo;
        return;
    }
    string s; for (int i = 0; i < n; i++) s += "1";
    for (auto x : indices) s[x] = '0';
    
    vector<int> leftHalf;
    vector<int> rightHalf;
    for (auto x : indices) {
        s[x] = '1';
        if (check_element(s)) {
            rightHalf.push_back(x);
        } else {
            leftHalf.push_back(x);
        }
        s[x] = '0';
    }

    checkStuff(perm, n, leftHalf, lo, (lo+hi)/2);
    checkStuff(perm, n, rightHalf, (lo+hi)/2+1, hi);
}

vector<int> restore_permutation(int n, int w, int r) {
    addStuff(n, "", "");
    compile_set();
    vector<int> perm(n);
    vector<int> indices(n); iota(indices.begin(), indices.end(), 0);

    checkStuff(perm, n, indices, 0, n-1);

    return perm;
}

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