Submission #203192

#	Time	Username	Problem	Language	Result	Execution time	Memory
203192		davitmarg	Unscrambling a Messy Bug (IOI16_messy)	C++17	100 / 100	7 ms	636 KiB

messy

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <ctype.h>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()

#ifndef  death
#include "messy.h"
#endif


using namespace std;


#ifdef death

map<string, bool> USED;
vector<int> P;

void add_element(string s)
{
	string t = s;
	for (int i = 0; i < P.size(); i++)
		t[i] = s[P[i]];
	cout << "ADD " << s << " = " << t << endl;
	USED[t] = 1;
}

void compile_set()
{

}

bool check_element(string s)
{
	cout << "CHECK " << s << " " << USED[s] << endl;
	return USED[s];
}

#endif

int n, w, r;
vector<int> p,ans;
string s;

void add(int l, int r)
{
	if (l == r)
		return;
	string x(n,'0');
	for (int i = r + 1; i < n; i++)
		x[i] = '1';
	for (int i = 0; i < l; i++)
		x[i] = '1';
	int m = (l + r) / 2;
	for (int i = l; i <= m; i++)
	{
		x[i] = '1';
		add_element(x);
		x[i] = '0';
	}
	add(l, m);
	add(m + 1, r);
}

string OR(string a, string b)
{
	for (int i = 0; i < n; i++)
		a[i] = max(a[i], b[i]);
	return a;
}

string solve(int l, int r,int k,string mask)
{
	//cout << l << " : " << r << " = " << mask << endl;
	string lmask = mask, rmask = mask, nmask = string(n, '0');
	int m = (l + r) / 2;
	for (int i = 0; i < n; i++)
		if (mask[i] == '0')
		{
			mask[i] = '1';
			int f = check_element(mask);
			if (f)
			{
				rmask[i] = '1';
				nmask[i] = '1';
			}
			else
				lmask[i] = '1';
			p[i] += k * !f;
			mask[i] = '0';
		}
	if (l+1 == r)
		return nmask;
	rmask = OR(rmask, solve(l, m, k / 2, lmask));
	return (nmask, solve(m + 1, r, k / 2, rmask));
}

int Main()
{
	p.resize(n);
	add(0, n - 1);
	compile_set();
	s = string(n, '0');
	solve(0, n - 1, n / 2, s);
	return 0;
}

vector<int> restore_permutation(int N, int W, int R)
{
	w = W;
	r = R;
	n = N;
	Main();
	ans = p;
	/*for (int i = 0; i < n; i++)
		ans[p[i]] = i;*/
	return ans;
}


#ifdef death

int main()
{
	int N, R=0, W=0;
	cin >> N;// >> W >> R;
	for (int i = 0; i < N; i++)
	{
		P.PB(0);
		cin >> P.back();
	}
	P = restore_permutation(N, W, R);
	for (int i = 0; i < N; i++)
		cout << P[i] << " ";
	cout << endl;
	return 0;
}

#endif

/*

8 0 0
1 7 3 2 5 0 4 6


*/

Compilation message (stderr)

messy.cpp: In function 'std::__cxx11::string solve(int, int, int, std::__cxx11::string)':
messy.cpp:115:45: warning: left operand of comma operator has no effect [-Wunused-value]
  return (nmask, solve(m + 1, r, k / 2, rmask));
                                             ^

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