oj.uz

Submission #54955

# Submission time Handle Problem Language Result Execution time Memory
54955 2018-07-05T14:22:21 Z zadrga ICC (CEOI16_icc) C++14
90 / 100
 173 ms 928 KB 
// 15.28
#include <icc.h>
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1LL << 55)
#define MOD (30013)
#define maxn 111

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

int id[maxn];
vector<int> comp[maxn], v[2];
int nn;

/*
bool query(int a, int b, int c[], int d[]){
	cout << "query: " <<endl;
	for(int i = 0; i < a; i++)
		cout << c[i] << " ";
	cout << endl;

	for(int i = 0; i < b; i++)
		cout << d[i] << " ";
	cout << endl;

	cout << endl;

	bool ret;
	cin >> ret;

	return ret;
}

void setRoad(int a, int b){
	cout << "setRoad " << a  << " " << b << endl << endl;
} */

bool ask(int l0, int d0, int l1, int d1){
	vector<int> a, b;
	for(int i = l0; i <= d0; i++)
		a.pb(v[0][i]);

	for(int i = l1; i <= d1; i++)
		b.pb(v[1][i]);

	return query(a.size(), b.size(), &a[0], &b[0]);
}

void merge(int a, int b){
	int posa = id[a];
	int posb = id[b];

	for(int i : comp[posb])
		comp[posa].pb(i);

	comp[posb].clear();

	nn = 0;
	for(int i = 1; i < maxn; i++){
		if(comp[i].size())
			comp[++nn] = comp[i];
	}

	for(int i = nn + 1; i < maxn; i++)
		comp[i].clear();

	for(int i = 1; i <= nn; i++){
	//	cout << i << ":  " << endl;
		for(int j : comp[i]){
			id[j] = i;
	//		cout << j << " "<< endl;
		}
	//	cout <<  endl << endl;
	} 
} 

void run(int n){
	nn = n;
	for(int i = 1; i <= n; i++){
		comp[i].pb(i);
		id[i] = i;
	}

	for(int edge_count = 0; edge_count < n - 1; edge_count++){
		for(int bit = 10; bit >= 0; bit--){
			if((1 << bit) > n)
				continue;

			v[0].clear();
			v[1].clear();

			for(int i = 1; i <= nn; i++){
				int pos = (i >> bit) & 1;
				for(int x : comp[i])
					v[pos].pb(x);
			}

			bool ret = ask(0, v[0].size() - 1, 0, v[1].size() - 1);
			if(ret == 1)
				break;
		}

		pii road;

		int l = 0, d = v[0].size() - 1, mid, ans = -1;
		while(l <= d){
			if(l == d){
				ans = l;
				break;
			}

			mid = (l + d) / 2;
			bool cur = ask(l, mid, 0, v[1].size() - 1);
			if(cur == 1)
				d = mid;

			else
				l = mid + 1;
		}

		road.fi = v[0][ans];


		l = 0; d = v[1].size() - 1; ans = -1;
		while(l <= d){
			if(l == d){
				ans = l;
				break;
			}

			mid = (l + d) / 2;
			bool cur = ask(0, v[0].size() - 1, l, mid);
			if(cur == 1)
				d = mid;

			else
				l = mid + 1;
		}

		road.se = v[1][ans];

		setRoad(road.fi, road.se);

		merge(road.fi, road.se);
	}
}

/*

int main(){
	int n;
	scanf("%d", &n);
	run(n);
	return 0;
}
*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 504 KB Ok! 115 queries used.
2 Correct 11 ms 504 KB Ok! 113 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 676 KB Ok! 596 queries used.
2 Correct 59 ms 732 KB Ok! 694 queries used.
3 Correct 62 ms 800 KB Ok! 680 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 888 KB Ok! 1561 queries used.
2 Correct 168 ms 888 KB Ok! 1705 queries used.
3 Correct 152 ms 888 KB Ok! 1649 queries used.
4 Correct 149 ms 888 KB Ok! 1644 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 888 KB Ok! 1650 queries used.
2 Correct 171 ms 888 KB Ok! 1663 queries used.
3 Correct 151 ms 888 KB Ok! 1631 queries used.
4 Correct 161 ms 888 KB Ok! 1650 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 928 KB Ok! 1620 queries used.
2 Correct 157 ms 928 KB Ok! 1623 queries used.
3 Correct 158 ms 928 KB Ok! 1693 queries used.
4 Correct 155 ms 928 KB Ok! 1651 queries used.
5 Correct 158 ms 928 KB Ok! 1585 queries used.
6 Correct 160 ms 928 KB Ok! 1691 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 156 ms 928 KB Too many queries! 1678 out of 1625
2 Halted 0 ms 0 KB -