oj.uz

Submission #605205

# Submission time Handle Problem Language Result Execution time Memory
605205 2022-07-25T13:53:23 Z sofapuden ICC (CEOI16_icc) C++14
100 / 100
 122 ms 620 KB 
#include "icc.h"
#include <bits/stdc++.h>
 
using namespace std;
 
int que(vector<int> a, vector<int> b){
 
	return query(a.size(), b.size(), a.data(), b.data());
}
 
void run(int n) {
	vector<vector<int>> comp(n);
	vector<int> cmp2(n);
	vector<int> ded(n,0);
	vector<int> uf(n+1);
	iota(uf.begin(),uf.end(),-1);
	for(int i = 0; i < n; ++i)comp[i].push_back(i+1);
 
	for(int i = 0; i < n; ++i){
		vector<int> a, b;
		vector<int> toche;
		for(int j = 0; (1<<j) < n-i; ++j)toche.push_back(j);
		reverse(toche.begin(),toche.end());
		int cu = 0;
		for(auto j : toche){
			cu = j;
			a.clear();
			b.clear();
			int cn = 0;
			for(int k = 0; k < n; ++k){
				if(ded[k])continue;
				cmp2[k] = cn;
				if(cn++ & (1<<j))for(auto x : comp[k])a.push_back(x);
				else for(auto x : comp[k])b.push_back(x);
			}
			if(!j)break;
			if(que(a,b))break;
		}
		int l = 0, r = a.size()-1, bes = 0; 
		while(l <= r){
			int m = (l + r) >> 1;
			vector<int> na;
			for(int i = 0; i <= m; ++i)na.push_back(a[i]);
			if(que(na,b)){
				bes = m;
				r = m-1;
			}
			else{
				l = m+1;
			}
		}
		int t1 = uf[a[bes]];
		vector<int> new_b;
		for(auto x : b){
			if((cmp2[uf[x]] & ~((1<<(cu+1))-1)) == (cmp2[t1] & ~((1<<(cu+1))-1)))new_b.push_back(x);
		}
		b = new_b;
		int l2 = 0, r2 = b.size()-1, bes2 = 0; 
		while(l2 <= r2){
			int m = (l2 + r2) >> 1;
			vector<int> nb;
			for(int i = 0; i <= m; ++i)nb.push_back(b[i]);
			if(que(a,nb)){
				bes2 = m;
				r2 = m-1;
			}
			else{
				l2 = m+1;
			}
		}
		setRoad(a[bes],b[bes2]);
		for(auto x : comp[uf[b[bes2]]])comp[uf[a[bes]]].push_back(x);
		ded[uf[b[bes2]]] = 1;
		for(auto x : comp[uf[b[bes2]]])uf[x] = uf[a[bes]];
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Ok! 111 queries used.
2 Correct 5 ms 468 KB Ok! 101 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 488 KB Ok! 525 queries used.
2 Correct 28 ms 492 KB Ok! 494 queries used.
3 Correct 29 ms 480 KB Ok! 519 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 496 KB Ok! 1286 queries used.
2 Correct 95 ms 492 KB Ok! 1201 queries used.
3 Correct 106 ms 488 KB Ok! 1290 queries used.
4 Correct 122 ms 488 KB Ok! 1274 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 492 KB Ok! 1241 queries used.
2 Correct 96 ms 508 KB Ok! 1253 queries used.
3 Correct 104 ms 588 KB Ok! 1286 queries used.
4 Correct 102 ms 484 KB Ok! 1265 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 492 KB Ok! 1257 queries used.
2 Correct 101 ms 468 KB Ok! 1287 queries used.
3 Correct 96 ms 496 KB Ok! 1271 queries used.
4 Correct 110 ms 484 KB Ok! 1297 queries used.
5 Correct 102 ms 488 KB Ok! 1300 queries used.
6 Correct 102 ms 496 KB Ok! 1329 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 496 KB Ok! 1270 queries used.
2 Correct 99 ms 620 KB Ok! 1285 queries used.