Submission #1226383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226383		vladilius	Unscrambling a Messy Bug (IOI16_messy)	C++20	70 / 100	1 ms	584 KiB

messy

#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

vector<int> restore_permutation(int n, int w, int r){
    auto f = [&](vector<int> t){
        string s;
        for (int i = 0; i < n; i++) s += '0';
        for (int i: t) s[i] = '1';
        return s;
    };
    
    vector<int> out(n), t;
    
    mt19937 rng((int) time(0));
    vector<int> o;
    for (int i = 0; i < n; i++){
        o.pb(i);
    }
    shuffle(o.begin(), o.end(), rng);
    
    for (int i = 0; i < 8; i++){
        t.pb(i);
        add_element(f(t));
    }
    
    function<void(int, int, int)> gen = [&](int d, int l, int r){
        if (l >= r) return;
        int m = (l + r) / 2;
        for (int i = l; i <= m; i++){
            vector<int> q;
            q.pb(d);
            q.pb(i);
            
            add_element(f(q));
        }
        
        gen(d + 1, l, m);
        gen(d + 1, m + 1, r);
    };
    gen(1, 8, n - 1);
    
    compile_set();
    
    string F;
    for (int i = 0; i < n; i++) F += '0';
    for (int i = 0; i < 8; i++){
        for (int j: o){
            if (F[j] == '0'){
                F[j] = '1';
                if (check_element(F)){
                    out[i] = j;
                    break;
                }
                F[j] = '0';
            }
        }
    }
    
    function<void(int, int, int, vector<int>)> solve = [&](int d, int l, int r, vector<int> vv){
        if (l > r) return;
        if (l == r){
            out[l] = vv[0];
            return;
        }
        
        int m = (l + r) / 2;
        
        vector<int> vv1, vv2;
        for (int i: vv){
            vector<int> q;
            q.pb(out[d]);
            q.pb(i);
            
            if (check_element(f(q))){
                vv1.pb(i);
            }
            else {
                vv2.pb(i);
            }
        }
        
        solve(d + 1, l, m, vv1);
        solve(d + 1, m + 1, r, vv2);
    };
    
    vector<int> vv;
    for (int i = 0; i < n; i++) vv.pb(i);
    for (int i = 0; i < 8; i++) vv.erase(find(vv.begin(), vv.end(), out[i]));
    solve(1, 8, n - 1, vv);
    
    vector<int> ans(n);
    for (int i = 0; i < n; i++){
        ans[out[i]] = i;
    }
    return ans;
}

Compilation message (stderr)

messy.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
messy_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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