Submission #101782

#	Time	Username	Problem	Language	Result	Execution time	Memory
101782		briansu	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	4 ms	512 KiB

messy

//{
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
typedef pair<ll,ll> ii;
#define REP(i,n) for(ll i=0;i<(n);i++)
#define REP1(i,n) for(ll i=1;i<=(n);i++)
#define FILL(i,n) memset(i,n,sizeof i)
#define X first
#define Y second
#define SZ(_a) (int)_a.size()
#define ALL(_a) _a.begin(),_a.end()
#define pb push_back
#ifdef brian
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif // brian
//}


const ll MAXn=1e5+5,MAXlg=__lg(MAXn)+2;
const ll MOD=1000000007;
const ll INF=ll(1e15);

#include <vector>

#include "messy.h"

ll ans[300];

void go(ll n, ll l, ll r, vector<ll> v)
{
    debug(n, l, r, v);
    if(l == r-1)
    {
        ans[l] = v[0];
        return;
    }
    string s = "";
    REP(i,n)s.pb('1');
    for(ll x:v)s[x] = '0';
    vector<ll> a, b;
    for(ll x:v)
    {
        s[x] = '1';
        debug(s);
        if(check_element(s))a.pb(x);
        else b.pb(x);
        s[x] = '0';
    }
    go(n, l, (l+r)/2, a);
    go(n, (l+r)/2, r, b);
}

std::vector<int> restore_permutation(int n, int w, int r) {
    string s = "";
    REP(i,n)s.pb('1');
    for(int len = n;len >= 2;len>>=1)
    {
        for(int l = 0;l < n;l += len)
        {
            REP(i, len)s[l + i] = '0';
            REP(i, len>>1)
            {
                s[l + i] = '1';
                add_element(s);
                s[l + i] = '0';
            }
            REP(i, len)s[l + i] = '1';
        }
    }
    debug("1");
    compile_set();
    vector<ll> v;
    REP(i,n)v.pb(i);
    go(n, 0, n, v);
    debug(2);
    vector<int> a(n);
    REP(i,n)a[ans[i]] = i; 
    return a;
}

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