Submission #117509

#	Time	Username	Problem	Language	Result	Execution time	Memory
117509		Meloric	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	4 ms	512 KiB

messy

#include <vector>

#include <iostream>
#include "messy.h"
#define pb push_back
#define pii pair<int, int>
#define X first
#define Y second

using namespace std;

vector<int> ans;
void start(int n, string a){
    if(n==0)return;
    int p1 = 0;
    string b = a;
    string c = a;
    while(a[p1] == '1')p1++;
    for(int i = 0; i < n; i++){
        a[p1+i] = '1';
        b[p1+i] = '1';
        c[p1+n+i] = '1';
        add_element(a);
        //cout << a << '\n';
        a[p1+i] = '0';
    }
    start(n/2, b);
    start(n/2, c);
}
void done(int n, string a, vector<int>& pos){
    if(n == 1){
        int tmp = 0;
        int pww = 1;
        for(int i = pos.size()-1; i >= 0; i--){
            tmp+=pos[i]*pww;
            pww*=2;
        }
        int p1 = 0;
        while(a[p1]!='0')p1++;
        ans[p1] = tmp;
        return;
    }
    string b = a;
    string c = a;
    int p1 = 0;
    for(int i = 0; i < n; i++){
        while(a[p1]=='1')p1++;
        a[p1] = '1';
        if(check_element(a)){
            c[p1] = '1';
        }else{
            b[p1] = '1';
        }
        a[p1] = '0';
        p1++;
    }
    vector<int> bpos = pos;
    vector<int> cpos = pos;
    bpos.pb(0); cpos.pb(1);
    done(n/2, b, bpos);
    done(n/2, c, cpos);
}
vector<int> restore_permutation(int n, int w, int r) {
    string a;
    ans.assign(n, 0);
    for(int i = 0; i< n; i++){
        a.pb('0');
    }
    vector<int> pos = {};
    start(n/2, a);
    compile_set();
    done(n, a, pos);
    //cout << "answer"<<'\n';
    //for(auto i : ans)cout << i << ' ';
    return ans;
    /*
    add_element("0");
    compile_set();
    check_element("0");*/
    //return vector<int>();
}

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