oj.uz

Submission #113776

# Submission time Handle Problem Language Result Execution time Memory
113776 2019-05-28T08:00:11 Z Mahdi_Jfri ICC (CEOI16_icc) C++14
100 / 100
 142 ms 704 KB 
#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 = 1e2 + 20;

vector<int> cmp[maxn];

int a[maxn] , b[maxn] , where[maxn] , x , y , pt = 1;
/*
int query(int sz1 , int sz2 , int* a , int* b)
{
	cout << "START" << endl;
	cout << sz1 << " " << sz2 << endl;
	for(int i = 0; i < sz1; i++)
		cout << a[i] << " ";
	cout << endl;

	for(int i = 0; i < sz2; i++)
		cout << b[i] << " ";
	cout << endl;
	int t = 0;
	for(int i = 0; i < sz1; i++)
		t += (a[i] == x || a[i] == y);

	if(t != 1)
		return 0;

	t = 0;
	for(int i = 0; i < sz2; i++)
		t += (b[i] == x || b[i] == y);

	if(t != 1)
		return 0;

	return 1;
}

void setRoad(int a , int b)
{
	cout << a << " " << b << " HOORAY" << endl;
	if(pt)
		cout << "HERE DONE" << endl;
	if(pt)
		pt-- , x = 2 , y = 3;
	else
		exit(0);
}
*/
pair<int , int> fn(int n)
{
	int pt1 = 0 , pt2 = 0;

	int sz = 31 - __builtin_clz(n);
	for(int k = 0; k <= sz; k++)
	{
		pt1 = 0 , pt2 = 0;
		for(int i = 1; i <= n; i++)
		{
			if((i >> k) & 1)
			{
				for(auto x : cmp[i])
					a[pt1++] = x;
			}
			else
			{
				for(auto x : cmp[i])
					b[pt2++] = x;
			}
		}

		if(k == sz || 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
		{
			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) , where[i] = i;

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

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

		for(int j = k + 1; j <= n - i; j++)
		{
			for(auto x : cmp[j])
				where[x] = j - 1;
			cmp[j - 1] = cmp[j];
			swap(cmp[j - 1] , cmp[j]);
		}
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 512 KB Ok! 94 queries used.
2 Correct 7 ms 512 KB Ok! 93 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 600 KB Ok! 522 queries used.
2 Correct 42 ms 512 KB Ok! 638 queries used.
3 Correct 43 ms 632 KB Ok! 650 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 620 KB Ok! 1411 queries used.
2 Correct 142 ms 512 KB Ok! 1591 queries used.
3 Correct 129 ms 604 KB Ok! 1531 queries used.
4 Correct 133 ms 700 KB Ok! 1524 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 632 KB Ok! 1446 queries used.
2 Correct 123 ms 704 KB Ok! 1494 queries used.
3 Correct 133 ms 568 KB Ok! 1611 queries used.
4 Correct 126 ms 512 KB Ok! 1473 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 636 KB Ok! 1592 queries used.
2 Correct 128 ms 512 KB Ok! 1602 queries used.
3 Correct 130 ms 608 KB Ok! 1598 queries used.
4 Correct 124 ms 512 KB Ok! 1580 queries used.
5 Correct 128 ms 604 KB Ok! 1492 queries used.
6 Correct 134 ms 512 KB Ok! 1585 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 512 KB Ok! 1594 queries used.
2 Correct 140 ms 572 KB Ok! 1588 queries used.