Submission #856627

#	Time	Username	Problem	Language	Result	Execution time	Memory
856627		LucaIlie	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	1 ms	628 KiB

messy

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

using namespace std;

string s0, s;
vector<int> ans;

void divide1( int l, int r ) {
    if ( l >= r )
        return;

    string s1 = s0;
    for ( int i = l; i <= r; i++ )
        s1[i] = '1';

    int mid = (l + r) / 2;
    for ( int i = l; i <= mid; i++ ) {
        s = s1;
        s[i] = '0';
        add_element( s );
    }

    divide1( l, mid );
    divide1( mid + 1, r );
}

void divide2( int l, int r, vector<int> v ) {
    if ( l > r )
        return;
    
    if ( l == r ) {
        ans[l] = v[0];
        return;
    }

    string s1 = s0;
    for ( int i: v )
        s1[i] = '1';

    int mid = (l + r) / 2;
    vector<int> leftt, rightt;
    for ( int i: v ) {
        s = s1;
        s[i] = '0';
        if ( check_element( s ) )
            leftt.push_back( i );
        else
            rightt.push_back( i );
    }

    divide2( l, mid, leftt );
    divide2( mid + 1, r, rightt );
}

vector<int> restore_permutation( int n, int w, int r ) {
    ans.resize( n );
    for ( int i = 0; i < n; i++ )
        s0 += '0';
    vector<int> v;
    for ( int i = 0; i < n; i++ )
        v.push_back( i );

    divide1( 0, n - 1 );
    compile_set();
    divide2( 0, n - 1, v );

    vector<int> perm( n );
    for ( int i = 0; i < n; i++ )
        perm[ans[i]] = i;

    return perm;
}

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