Submission #431326

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

messy

#include <bits/stdc++.h>
#include "messy.h"
using namespace std;
#define F first
#define S second
using ll=long long;
using pii=pair<int,int>;
vector<int>ans;
void generate_add(int sz, int pos, string s)
{
	if(sz == 1) return;
	for(int i=pos;i<pos+sz/2;i++)
	{
		s[i] = '1';
		add_element(s);
		s[i] = '0';
	}
	for(int i=pos+sz/2;i<pos+sz;i++) s[i] = '1';
	generate_add(sz>>1, pos, s);
	for(int i=pos+sz/2;i<pos+sz;i++) s[i] = '0';
	s[pos] = '1';
	generate_add(sz>>1, pos+sz/2, s);
	s[pos] = '0';
}

void search_rescue(int sz, int pos, vector<int>res, string s)
{
	//cerr<<sz<<' '<<pos<<" :";
	//for(int i : res) cerr<<i<<',';cerr<<endl;
	if(sz==1)
	{
		ans[pos] = res[0];
		return;
	}
	vector<int> fir, sec;
	for(int i=0;i<sz;i++)
	{
		s[res[i]] = '1';
		if(check_element(s)) fir.emplace_back(res[i]);
		else sec.emplace_back(res[i]);
		s[res[i]] = '0';
	}
	
	for(int i : sec) s[i] = '1';
	search_rescue(sz>>1, pos, fir, s);
	for(int i : sec) s[i] = '0';

	s[ans[pos]] = '1';
	search_rescue(sz>>1, pos+sz/2, sec, s);
	s[ans[pos]] = '0';
}
vector<int> restore_permutation(int n, int w, int r) {
    string s = "";
    vector<int>_res;
    for(int i=0;i<n;i++) _res.emplace_back(i);
    for(int i=0;i<n;i++) ans.emplace_back(-1);
    for(int i=0;i<n;i++) s+='0';
    
    generate_add(n,0,s);
    compile_set();
    search_rescue(n,0,_res,s);
    //add_element("0");
    //check_element("0");
    vector<int>ans2(n);
    for(int i=0;i<n;i++) ans2[ans[i]]=i;
    return ans2;
}

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