Submission #1111659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111659		Gray	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	2 ms	804 KiB

messy

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define INF 2e18
#include "messy.h"

void add_element_connector(string &s){
    add_element(s);
    // cout << "Add: " << s << endl;
}
bool check_element_connector(string &s){
    bool res=check_element(s);
    // cout << "Check: " << s << ": " << res << endl;
    return res;
}
void gen(ll l, ll r, ll n){
    if (l>=r) return;
    string s = ""; for (ll i=0; i<n; i++) s+="1";
    for (ll i=l; i<=r; i++) s[i]='0';
    ll mid = (l+r)/2;
    for (ll i=l; i<=mid; i++){
        s[i]='1';
        add_element_connector(s);
        s[i]='0';
    }
    gen(l, mid, n); gen(mid+1, r, n);
}

void restore(ll l, ll r, ll n, vector<ll> mem, vector<int> &perm){
    if (l==r){
        perm[mem[0]]=l;
        return;
    }
    string s = "";
    for (ll i=0; i<n; i++) s+='1';
    for (auto i:mem) s[i]='0';
    vector<ll> lmem, rmem;
    for (auto i:mem){
        s[i]='1';
        if (check_element_connector(s)) lmem.push_back(i);
        else rmem.push_back(i);
        s[i]='0';
    }
    ll mid = (l+r)/2;
    restore(l, mid, n, lmem, perm);
    restore(mid+1, r, n, rmem, perm);
}

std::vector<int> restore_permutation(int n, int w, int r) {
    gen(0, n-1, n);
    compile_set();
    vector<int> perm(n);
    vector<ll> mem; for (ll i=0; i<n; i++) mem.push_back(i);
    restore(0, n-1, n, mem, perm);
    return perm;
}

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