Submission #24523

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
24523	2017-06-09T18:26:17 Z	rubabredwan	ICC (CEOI16_icc)	C++14	90 / 100	163 ms	2268 KB

icc

/* Bismillahir Rahmanir Rahim */
 
#include <bits/stdc++.h>
#include "icc.h"
 
using namespace std;
 
const int N = 105;
 
int n, par[N], mat[N][N];
set<int>comp;
vector<int>nudes[N];
 
int Find(int at){
	return par[at] == at ? at : par[at] = Find(par[at]);
}
 
void Union(int a, int b){
	int x = Find(a);
	int y = Find(b);
	for(auto u : nudes[y]){
		nudes[x].push_back(u);
	}
	par[y] = x;
	comp.erase(y);
}

 
int fuk[N], tt;
 
int get(int sa, int sb, int a[], int b[]){
	int lo = 0, hi = sb - 1;
	while(lo < hi){
		int mid = (lo + hi) / 2; tt = 0;
		for(int i=lo;i<=mid;i++) fuk[tt] = b[i], ++tt;
		if(query(sa, tt, a, fuk)) hi = mid;
		else lo = mid + 1;
	}
	return b[lo];
}
 
int aa[N], bb[N], cr[N];
int sa, sb, sz;
 
void run(int _n){
	srand(time(NULL));
	n = _n;
	comp.clear();
	for(int i=1;i<=n;i++){
		par[i] = i;
		comp.insert(i);
		nudes[i].push_back(i);
	}
	for(int road = 1; road < n; ++road){
		sz = 0;
		for(auto u : comp) cr[++sz] = u;
		vector<int>rnd;
		for(int bit = 0; bit <= 7; ++bit) rnd.push_back(bit);
		random_shuffle(rnd.begin(), rnd.end());
		for(auto bit : rnd){
			sa = 0, sb = 0;
			for(int i = 1; i <= sz; ++i){
				if(i & (1 << bit)) for(auto v : nudes[cr[i]]) aa[sa] = v, ++sa;
				else for(auto v : nudes[cr[i]]) bb[sb] = v, ++sb;
			}
			if(sa == 0 || sb == 0) continue;
			if(query(sa, sb, aa, bb)){
				int x = get(sa, sb, aa, bb);
				int y = get(sb, sa, bb, aa);
				Union(x, y);
				setRoad(x, y);
				break;
			}
		}
	}
}

Subtask #1

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	2132 KB	Ok! 100 queries used.
2	Correct	6 ms	2136 KB	Ok! 99 queries used.

Subtask #2

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	2136 KB	Ok! 535 queries used.
2	Correct	43 ms	2140 KB	Ok! 659 queries used.
3	Correct	43 ms	2136 KB	Ok! 663 queries used.

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	126 ms	2264 KB	Ok! 1451 queries used.
2	Correct	139 ms	2264 KB	Ok! 1675 queries used.
3	Correct	129 ms	2268 KB	Ok! 1627 queries used.
4	Correct	126 ms	2268 KB	Ok! 1526 queries used.

Subtask #4

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	116 ms	2268 KB	Ok! 1481 queries used.
2	Correct	129 ms	2268 KB	Ok! 1489 queries used.
3	Correct	139 ms	2268 KB	Ok! 1635 queries used.
4	Correct	133 ms	2264 KB	Ok! 1490 queries used.

Subtask #5

29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	153 ms	2268 KB	Ok! 1633 queries used.
2	Correct	139 ms	2264 KB	Ok! 1635 queries used.
3	Correct	136 ms	2264 KB	Ok! 1656 queries used.
4	Correct	139 ms	2264 KB	Ok! 1609 queries used.
5	Correct	163 ms	2268 KB	Ok! 1479 queries used.
6	Correct	153 ms	2268 KB	Ok! 1588 queries used.

Subtask #6

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	133 ms	2268 KB	Too many queries! 1653 out of 1625
2	Halted	0 ms	0 KB	-