Submission #138879

#	Time	Username	Problem	Language	Result	Execution time	Memory
138879		arthurconmy	Unscrambling a Messy Bug (IOI16_messy)	C++14	0 / 100	5 ms	488 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[i-n]=group[i][0];
		cout << ans[i-n] << endl;
	}

	return {};
}

#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