Submission #377357

#	Time	Username	Problem	Language	Result	Execution time	Memory
377357		rrrr10000	Unscrambling a Messy Bug (IOI16_messy)	C++14	100 / 100	3 ms	620 KiB

messy

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define rosrt(a) {sort(all(a));reverse(all(a));}
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define pb emplace_back
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];};cout<<'\n';}
template<class T> void outvv(T v){for(auto x:v)outv(x);}
template<class T> void outp(T p){cout<<'('<<p.fi<<','<<p.se<<')'<<endl;}
template<class T> void outvp(T v){for(auto x:v)cout<<'('<<x.fi<<','<<x.se<<')';cout<<endl;}
#include "messy.h"
vector<int> restore_permutation(int n,int w,int r){
    vector<int> ask(n);
    rep(i,n)ask[i]=i;
    function<void(vector<int>)> dfs=[&](vector<int> v){
        if(v.size()==1)return;
        string s;
        rep(i,n)s+='1';
        rep(i,v.size())s[v[i]]='0';
        rep(i,v.size()/2){
            s[v[i]]='1';
            add_element(s);
            s[v[i]]='0';
        }
        vector<int> a,b;
        rep(i,v.size()/2)a.pb(v[i]);
        REP(i,v.size()/2,v.size())b.pb(v[i]);
        dfs(a);dfs(b);
    };dfs(ask);
    vector<int> ans(n);
    compile_set();
    function<void(vector<int>,vector<int>)> dfs2=[&](vector<int> v,vector<int> to){
        // outv(to);outv(v);
        if(v.size()==1){
            ans[to[0]]=v[0];return;
        }
        string s;
        rep(i,n)s+='1';
        rep(i,v.size())s[to[i]]='0';
        vector<int> ato,bto,a,b;
        rep(i,v.size()){
            s[to[i]]='1';
            if(check_element(s))ato.pb(to[i]);
            else bto.pb(to[i]);
            s[to[i]]='0';
        }
        rep(i,v.size()/2)a.pb(v[i]);
        REP(i,v.size()/2,v.size())b.pb(v[i]);
        // outv(ato);outv(bto);
        dfs2(a,ato);dfs2(b,bto);
    };dfs2(ask,ask);
    return ans;
}

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