Submission #718040

#	Time	Username	Problem	Language	Result	Execution time	Memory
718040		myrcella	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	2 ms	468 KiB

messy

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

#include "messy.h"

vector <int> ans;
int N;

void solve(vector<int> pos) {
	if (SZ(pos)==1) return;
	int mid = SZ(pos)>>1;
	string s;
	rep(i,0,N) s+="1";
	for (int v:pos) s[v] = '0';
	vector <int> pl,pr;
	rep(i,0,mid) {
		int v = pos[i];
		s[v] = '1';
		add_element(s);
		s[v] = '0';
		pl.pb(v);
	}
	rep(i,mid,SZ(pos)) pr.pb(pos[i]);
	
	solve(pl);
	solve(pr);
}

void query(vector <int> pos,vector <int> val) {
	if (SZ(pos)==1) {
		ans[val[0]] = pos[0];
		return;
	}
	string q;
	rep(i,0,N) q+="1";
	for (int v:val) q[v] = '0';
	vector <int> vl,vr;
	for (int v:val) {
		q[v] = '1';
		if (check_element(q)) vl.pb(v);
		else vr.pb(v);
		q[v] = '0';
	}
	vector <int> pl,pr;
	rep(i,0,SZ(pos)/2) pl.pb(pos[i]),pr.pb(pos[i+SZ(pos)/2]);
	query(pl,vl),query(pr,vr);
}

std::vector<int> restore_permutation(int n, int w, int r) {
	N=n;
	ans.resize(n);
	vector <int> p,v;
	rep(i,0,n) p.pb(i),v.pb(i);
	solve(p);
	compile_set();
	query(p,v);
    return ans;
}

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