Submission #721044

#	Time	Username	Problem	Language	Result	Execution time	Memory
721044		yuuhi	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	3 ms	468 KiB

messy

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

#define f first
#define s second
#define _size(x) ((int)((x).size()))

using namespace std ;

typedef pair< long long , long long > ii ;

const int maxN = 200 + 10 ;
const int oo = 1e9 + 10 ;
mt19937 rng(time(nullptr)) ;

vector< int > restore_permutation (int n , int W , int R) {
    vector< int > st(n) ;
    iota(st.begin() , st.end() , 0) ;
    vector< int > p(n) ;

    function< void(int , int) > init = [&](int l , int r) {
        if (l == r) return ;
        int mid = (l + r) >> 1 ;
        string s(n , '1') ;
        for (int i = l ; i <= r ; ++ i) s[i] = '0' ;
        for (int i = l ; i <= mid ; ++ i) {
            s[i] = '1' ;
            add_element(s) ;
            s[i] = '0' ;
        }
        init(l , mid) ;
        init(mid + 1 , r) ;
    };

    function< void(int , int , vector< int >) > solve = [&](int l , int r , vector< int > st) {
        if (l == r) {
            p[st[0]] = l ;
            return ;
        }

        int mid = (l + r) >> 1 ;
        string s(n , '1') ;
        for (int i : st) s[i] = '0' ;
        vector< int > lef , rig ;
        for (int i : st) {
            s[i] = '1' ;
            if (check_element(s)) lef.push_back(i) ;
            else rig.push_back(i) ;
            s[i] = '0' ;
        }

        solve(l , mid , lef) ;
        solve(mid + 1 , r , rig) ;
    };

    init(0 , n - 1) ;
    compile_set() ;
    solve(0 , n - 1 , st) ;
    return p ;
}

//int main() {
//    #define name "abc"
//    if (fopen(name".inp" , "r")) {
//        freopen(name".inp" , "r" , stdin) ;
//        freopen(name".out" , "w" , stdout) ;
//    }
//    ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
//
//    return 0 ;
//}

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