Submission #605205

#	Time	Username	Problem	Language	Result	Execution time	Memory
605205		sofapuden	ICC (CEOI16_icc)	C++14	100 / 100	122 ms	620 KiB

icc

#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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10