oj.uz

Submission #54958

# Submission time Handle Problem Language Result Execution time Memory
54958 2018-07-05T14:31:58 Z zadrga ICC (CEOI16_icc) C++14
100 / 100
 221 ms 876 KB 
/*
Idea:
- http://www.ceoi2016.ro/competition/tasks/ (ICC solution)
*/

#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 = 0; (1 << bit) <= n; bit++){
			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 9 ms 504 KB Ok! 98 queries used.
2 Correct 10 ms 504 KB Ok! 99 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 628 KB Ok! 509 queries used.
2 Correct 52 ms 628 KB Ok! 639 queries used.
3 Correct 71 ms 652 KB Ok! 640 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 664 KB Ok! 1399 queries used.
2 Correct 176 ms 732 KB Ok! 1608 queries used.
3 Correct 168 ms 732 KB Ok! 1601 queries used.
4 Correct 166 ms 740 KB Ok! 1513 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 740 KB Ok! 1440 queries used.
2 Correct 151 ms 868 KB Ok! 1459 queries used.
3 Correct 197 ms 868 KB Ok! 1566 queries used.
4 Correct 161 ms 868 KB Ok! 1484 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 868 KB Ok! 1577 queries used.
2 Correct 190 ms 868 KB Ok! 1579 queries used.
3 Correct 221 ms 868 KB Ok! 1616 queries used.
4 Correct 171 ms 868 KB Ok! 1587 queries used.
5 Correct 161 ms 876 KB Ok! 1456 queries used.
6 Correct 164 ms 876 KB Ok! 1537 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 876 KB Ok! 1586 queries used.
2 Correct 178 ms 876 KB Ok! 1608 queries used.