Submission #113750

#	Time	Username	Problem	Language	Result	Execution time	Memory
113750		Mahdi_Jfri	ICC (CEOI16_icc)	C++14	0 / 100	363 ms	596 KiB

icc

#include<bits/stdc++.h>
#include "icc.h"
using namespace std;

#define ll long long
#define pb push_back

auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937 rnd(seed);

const int maxn = 1e3 + 20;

vector<int> cmp[maxn];

int a[maxn] , b[maxn] , where[maxn];

bool is[maxn];

pair<int , int> fn(int n)
{
	int pt1 = 0 , pt2 = 0;
	while(1)
	{
		pt1 = 0 , pt2 = 0;
		for(int i = 0; i < n; i++)
		{
			if(rnd() % 2)
			{
				is[i] = 1;
				for(auto x : cmp[i])
					a[pt1++] = x;
			}
			else
			{
				is[i] = 0;
				for(auto x : cmp[i])
					b[pt2++] = x;
			}
		}

		if(query(pt1 , pt2 , a , b))
			break;
	}

	vector<int> x , y;
	for(int i = 0; i < pt1; i++)
		x.pb(a[i]);
	for(int i = 0; i < pt2; i++)
		y.pb(b[i]);

	while((int)y.size() > 1)
	{
		for(int i = 0; i < (int)y.size() / 2; i++)
			b[i] = y[i];
		pt2 = y.size() / 2;

		if(query(pt1 , pt2 , a , b))
		{
			y.clear();
			for(int i = 0; i < pt2; i++)
				y.pb(b[i]);
		}
		else
		{
			y.clear();
			vector<int> tmp;
			for(int i = pt2; i < (int)y.size(); i++)
				tmp.pb(y[i]);
			y = tmp;
		}
	}

	swap(x , y);
	pt1 = x.size();
	for(int i = 0; i < pt1; i++)
		a[i] = x[i];

	while((int)y.size() > 1)
	{
		for(int i = 0; i < (int)y.size() / 2; i++)
			b[i] = y[i];
		pt2 = y.size() / 2;

		if(query(pt1 , pt2 , a , b))
		{
			y.clear();
			for(int i = 0; i < pt2; i++)
				y.pb(b[i]);
		}
		else
		{
			vector<int> tmp;
			for(int i = pt2; i < (int)y.size(); i++)
				tmp.pb(y[i]);
			y = tmp;
		}
	}

	setRoad(x[0] , y[0]);
	return make_pair(x[0] , y[0]);
}

void run(int n)
{
	for(int i = 1; i <= n; i++)
		cmp[i].pb(i);

	for(int i = 0; i < n - 1; i++)
	{
		auto tmp = fn(n - i);
		int v = tmp.first , u = tmp.second;

		for(auto x : cmp[where[u]])
			where[x] = where[v] , cmp[where[v]].pb(x);

		for(int j = where[u] + 1; j < n - i; j++)
			cmp[j].swap(cmp[j - 1]);
	}
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10