Submission #32072

#	Time	Username	Problem	Language	Result	Execution time	Memory
32072		osmanorhan	Unscrambling a Messy Bug (IOI16_messy)	C++14	70 / 100	10 ms	2432 KiB

messy

#include "messy.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all( x ) x.begin(), x.end()
#define umin( x, y ) x = min( x, (y) )
#define umax( x, y ) x = max( x, (y) )

using namespace std;

typedef long long Lint;
typedef pair<int,int> ii;

const int maxn = 220;

int n, W, R;
vector<int> ans;
vector<int> known;
int kn[maxn];
map<string,int> mp;
set<int> st[maxn];

int num( string s ) {
    int ret = 0;
    for(int i=0;i<s.size();i++) if( s[i] == '1' ) ret++;
    return ret;
}

void add( int x, int k, int t ) {
    string s = "";
    for(int i=0;i<n;i++) s += !k + '0';
    for(int i=0;i<known.size();i++)
        s[known[i]] = '0' + k;
    s[x] = k + '0';
    if( num( s ) != t || mp.count( s ) ) return;
    mp[s] = 1;
    //cout << "added " << s << endl;

    assert( --W >= 0 );
    add_element( s );
}

bool check( int x, int k, int t ) {
    string s = "";
    for(int i=0;i<n;i++) s += !k + '0';
    for(int i=0;i<known.size();i++)
        s[known[i]] = '0' + k;
    s[x] = k + '0';
    if( num( s ) != t ) return false;
    assert( mp.count(s) == 0 );
    mp[s] = 1;
    //cout << "checked " << s << endl;
    assert( --R >= 0 );
    return check_element( s );
}

vector<int> restore_permutation(int N, int w, int r) {
    W = w;
    R = r;
    n = N;
    ans.resize( n );

    for(int i=1;(1<<i)<=n;i++) {
        add( i-1, 0, n-i );
        int h = n / (1<<i);
        for(int j=0;j<n;j++)
            if( (j/h)%2 == 0 ) add( j, 1, i );

        known.pb( i-1 );
    }
    compile_set();

    known.clear();
    mp.clear();

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            st[i].insert( j );
    int last = 0;
    for(int i=1;(1<<i)<=n;i++) {
        last = i;
        int loc = -1;
        for(int j=0;j<n;j++)
            if( check( j, 0, n-i ) ) {
                loc = j;
                break;
            }
        assert( loc >= 0 );
        ans[i-1] = loc;
        for(int j=i;j<n;j++)
            st[j].erase( loc );

        int h = n / (1<<i);

        vector<int> v1, v0;
        for(int j=0;j<n;j++) {
            if( check( j, 1, i ) ) {
                v1.pb( j );
            } else v0.pb( j );
        }

        for(int j=0;j<n;j++) {
            if( (j/h)%2 == 0 ) {
                for(int k=0;k<v0.size();k++)
                    st[j].erase( v0[k] );
            } else {
                for(int k=0;k<v1.size();k++)
                    st[j].erase( v1[k] );
            }
        }

        known.pb( loc );
        kn[loc] = 1;
    }

    for(int i=0;i<n;i++) {
            if( i < last ) continue;
        assert( st[i].size() == 1 );
        ans[i] = *st[i].begin();
    }
    //for(int i=0;i<n;i++) printf("%d ",ans[i]); printf("--- ans\n");
    vector<int> re(n);
    for(int i=0;i<n;i++) re[ ans[i] ] = i;
    return re;
}

Compilation message (stderr)

messy.cpp: In function 'int num(std::__cxx11::string)':
messy.cpp:26:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<s.size();i++) if( s[i] == '1' ) ret++;
                 ~^~~~~~~~~
messy.cpp: In function 'void add(int, int, int)':
messy.cpp:33:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<known.size();i++)
                 ~^~~~~~~~~~~~~
messy.cpp: In function 'bool check(int, int, int)':
messy.cpp:47:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<known.size();i++)
                 ~^~~~~~~~~~~~~
messy.cpp: In function 'std::vector<int> restore_permutation(int, int, int)':
messy.cpp:105:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int k=0;k<v0.size();k++)
                             ~^~~~~~~~~~
messy.cpp:108:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int k=0;k<v1.size();k++)
                             ~^~~~~~~~~~

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