제출 #138881

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
138881		arthurconmy	Unscrambling a Messy Bug (IOI16_messy)	C++14	0 / 100	4 ms	508 KiB

messy

#include <bits/stdc++.h>
 
#ifndef ARTHUR_LOCAL
	#include "messy.h"
#endif
 
using namespace std;
 
#ifdef ARTHUR_LOCAL
	map<string,bool> pres;
 
	void add_element(string S)
	{
		cout << S << endl;
	}
 
	void compile_set()
	{
		cout << "COMPILED" << endl;
	}
 
	bool check_element(string S)
	{
		//cout << S << endl;
 
		//reverse(S.begin(),S.end());
 
		//cout << S << endl;
 
		//cout << pres[S] << endl;
 
		return pres[S];
	}
#endif
 
vector<int> restore_permutation(int n, int w, int r) 
{
/*    add_element("0");
    compile_set();
    check_element("0");
    return std::vector<int>();*/
 
    #ifdef ARTHUR_LOCAL
    	cout << "IGNORE: " << w+r << endl;
    #endif
 
	for(int no_groups=2; no_groups<=n; no_groups*=2)
	{
		for(int g=0; g<no_groups; g+=2)
		{
			for(int i=0; i<int(n/no_groups); i++)
			{
				string S = "";
 
				for(int d=1; d <= g*int(n/no_groups); d++) S+='1';
				for(int d=1; d <= i; d++) S+='0';
 
				S+='1';
 
				for(int d=1; d < int(n/no_groups) - i; d++) S+='0';
				for(int d=1; d <= int(n/no_groups); d++) S+='0';
 
				while(int(S.size())<n) S+='1';
 
				add_element(S);
				//pres[S]=1;
			}
		}
	}
 
	compile_set();
 
	vector<vector<int>> group(4*n); // kinda like a segment tree (indexing) I guess
 
	for(int i=0; i<n; i++) group[1].push_back(i); // initially we know fuck all about everything
 
	for(int no_groups=1; no_groups<n; no_groups*=2) // this is the number of groups we have at this stage
	{
		for(int g=0; g<no_groups; g++)
		{
			string S="";
 
			for(int i=0; i<n; i++) S+='0';
 
			for(int i=no_groups; i<no_groups*2; i++)
			{
				if(i != no_groups+g)
				{
					for(auto u:group[i]) S[u]='1';
				}
			}
 
			//cout << no_groups << " " << g << " " << S << endl;
 
			for(auto u:group[no_groups+g])
			{
				string S2 = S;
				S2[u]='1';
 
				if(check_element(S2))
				{
					group[2*(no_groups+g)].push_back(u);
					//cout << 2*(no_groups+g) << " gets " << u << endl;
				}
 
				else
				{
					group[2*(no_groups+g) + 1].push_back(u);
					//cout << 2*(no_groups+g) + 1 << " gets " << u << endl;
				}
			}
		}
	}
 
	vector<int> ans(n);
 
	for(int i=n; i<n+n; i++)
	{
		ans[group[i][0]]=i-n;
		cout << ans[i-n] << endl;
	}
 
	return ans;
}
 
#ifdef ARTHUR_LOCAL
	int main()
	{
		restore_permutation(8,0,0);
	}
#endif

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