Submission #125762

#	Time	Username	Problem	Language	Result	Execution time	Memory
125762		Nodir_Bobiev	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	5 ms	988 KiB

messy

# include <iostream>
# include <vector>
# include <algorithm>
# include "messy.h"

using namespace std;

vector < string > vc, jj;
vector < int > tri[130][130];
string zeros, ones;
/*
void add_element( string s ){ jj.push_back( s );}

void compile_set()
{
    vector < int > p = {0,6,7,1,4,2,3,5};
    for( auto s: jj ){
        string nw;
        for( auto c: p ){
            nw += s[c];
        }
        vc.push_back( nw );
    }
}

bool check_element( string s )
{
    for( auto c: vc )
        if( c == s ) return true;
    return false;
}

void print_elements()
{
    for( auto c: vc ) cout << c << endl;
}
*/

void rec( int i, int j )
{
    if( j == 1 )    return;

    string ss = ones;
    for( auto c: tri[i][j] )ss[c] = '0';

    for( auto c: tri[i][j] ){
        string s = ss;
        s[c] = '1';
        if( check_element( s ) )
            tri[i][j/2].push_back( c );
        else
            tri[i+j/2][j/2].push_back( c );
        s[c] = '0';
    }
    rec(   i,   j/2 );
    rec( i+j/2, j/2);
}

vector <int> restore_permutation( int n, int w, int r )
{
    for( int i = 0; i < n; i ++ ){  zeros += '0';  ones += '1';  }

    for( int i = 2; i <= n; i *= 2 ){
        for( int j = 0; j < n; j += i ){
            string s = zeros;
            for( int k = 0; k < j; k ++ ) s[k] = '1';
            for( int k=j+i; k < n; k ++ ) s[k] = '1';
            for( int k = j; k<j+i/2; k ++ ){
                s[k] = '1';
                add_element( s );
                s[k] = '0';
            }
        }
    }

    for( int i = 0; i < n; i ++ )
        tri[0][n].push_back( i );

    compile_set();
    //print_elements();

    rec( 0, n );

    vector < pair < int, int > > st;
    for( int i = 0; i < n; i ++ ){
        st.push_back( make_pair( tri[i][1][0], i ) );
    }

    sort( st.begin(), st.end() );

    vector < int > ret;
    for( auto c: st )
        ret.push_back( c.second );

    return ret;
}
/*
int main()
{
    vector < int > ans;
    ans = restor_permutation( 8,8,8 );
    for( auto c: ans )
        cout << c << ' ';

    return 0;
}
*/

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