Submission #420055

#	Time	Username	Problem	Language	Result	Execution time	Memory
420055		errorgorn	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	3 ms	464 KiB

messy

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include "messy.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;

void dnc_w(vector<int> proc){
	if (sz(proc)==1) return;
	
	set<int> in;
	for (auto &it:proc) in.insert(it);
	
	string s(n,'0');
	rep(x,0,n) if (!in.count(x)) s[x]='1';
	
	rep(x,0,sz(proc)/2){
		s[proc[x]]='1';
		add_element(s);
		s[proc[x]]='0';
	}
	
	vector<int> l,r;
	rep(x,0,sz(proc)/2) l.pub(proc[x]);
	rep(x,sz(proc)/2,sz(proc)) r.pub(proc[x]);
	
	dnc_w(l),dnc_w(r);
}

vector<int> ans;

void dnc_r(vector<int> proc,vector<int> val){
	if (sz(proc)==1){
		ans[proc[0]]=val[0];
		return;
	}
	
	set<int> in;
	for (auto &it:proc) in.insert(it);
	
	string s(n,'0');
	rep(x,0,n) if (!in.count(x)) s[x]='1';
	
	vector<int> l,r;
	vector<int> lval,rval;
	
	rep(x,0,sz(proc)){
		s[proc[x]]='1';
		if (check_element(s)) l.pub(proc[x]);
		else r.pub(proc[x]);
		s[proc[x]]='0';
	}
	
	rep(x,0,sz(proc)/2) lval.pub(val[x]);
	rep(x,sz(proc)/2,sz(proc)) rval.pub(val[x]);
	
	dnc_r(l,lval),dnc_r(r,rval);
}

std::vector<int> restore_permutation(int N,int W,int R) {
	n=N;
	rep(x,0,n) ans.pub(0);
	
	vector<int> proc;
	rep(x,0,n) proc.pub(x);
	
	dnc_w(proc);
	
	compile_set();
	
	dnc_r(proc,proc);
	
	return ans;
}

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