제출 #419891

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

messy

#include <bits/stdc++.h>

#include "messy.h"

using namespace std;

void add(vector<int> v, string s, int y, int n){
    if((1<<y) >= n) return;
    vector<int> v1, v2;
    for(int x : v){
        if(x&(1<<y)){
            s[x] = '1';
            add_element(s);
            s[x] = '0';
            v2.push_back(x);
        } else
            v1.push_back(x);
    }
    string s2 = s;
    for(int x : v2)
        s2[x] = '1';
    add(v1, s2, y+1, n);
    s2 = s;
    for(int x : v1)
        s2[x] = '1';
    add(v2, s2, y+1, n);
}

vector<int> ret;
void megold(vector<int> v, string s, int y, int n){
    if((1<<y) >= n) return;
    vector<int> v1, v2;
    for(int x : v){
        s[x] = '1';
        if(check_element(s)){
            v2.push_back(x);
            ret[x] += (1<<y);
        } else
            v1.push_back(x);
        s[x] = '0';
    }
    string s2 = s;
    for(int x : v2)
        s2[x] = '1';
    megold(v1, s2, y+1, n);
    s2 = s;
    for(int x : v1)
        s2[x] = '1';
    megold(v2, s2, y+1, n);
}

std::vector<int> restore_permutation(int n, int w, int r) {
    ret.resize(n, 0);
    string s;
    s.assign(n, '0');
    vector<int> v(n);
    iota(v.begin(), v.end(), 0);
    add(v, s, 0, n);
    compile_set();
    megold(v, s, 0, n);

    return ret;
}

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