Submission #139853

#	Time	Username	Problem	Language	Result	Execution time	Memory
139853		ibrahim001	Unscrambling a Messy Bug (IOI16_messy)	C++14	49 / 100	3 ms	376 KiB

messy

#include "messy.h"
#include <bits/stdc++.h>
#define intt long long
#define pb push_back
#define F first
#define S second
#define pii pair<int,int>
using namespace std;
int i,j;
vector<int> restore_permutation(int n, int w, int r) {
    vector<int>ans(n,0);
    srand(time(0));
    vector<int>v;
    for ( i = 0; i < n; i++ )
    {
        v.pb(i);
    }
    random_shuffle(v.begin(),v.end());
    string s = "";
    for ( i = 1; i <= n; i++ )
    {
        s+='0';
    }
    for ( int i : v )
    {
        s[i]='1';
        add_element(s);
    }
    compile_set();
    set<int>st,st1;
    for ( i = 0; i < n; i++ )
    {
        st.insert(i);
        st1.insert(i);
        s[i] = '0';
    }
    for ( i = 0; i < n-1; i++ )
    {
        bool used[n];
        for( j = 0; j < n; j++ )
            used[j]=false;
        while(true)
        {
            j = rand()%n;
            if ( used[j] )
                continue;
            used[j]=true;
            if ( s[j] != '1' )
            {
                s[j] = '1';
                if (check_element(s))
                {
                    st.erase(v[i]);
                    st1.erase(j);
                    ans[j] = v[i];
                    break;
                }
                s[j]='0';
            }
        }
    }
    ans[*st1.begin()] = *st.begin();
    return ans;
}

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