Submission #605823

#	Time	Username	Problem	Language	Result	Execution time	Memory
605823		HappyPacMan	ICC (CEOI16_icc)	C++14	100 / 100	117 ms	504 KiB

icc

#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
int reqA[104],reqB[104],DSU[104];
 
int par(int u){
	return DSU[u] = DSU[u] == u ? u : par(DSU[u]);
}
void join(int x,int y){
	x = par(x);
	y = par(y);
	DSU[x] = y;
}
 
void run(int N){
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	iota(DSU,DSU+104,0);
	for(int i=1;i<N;i++){
		set<int> st;
		vector<int> vec[104];
		for(int j=1;j<=N;j++){
			par(j);
			st.emplace(DSU[j]);
			vec[DSU[j]].emplace_back(j);
		}
		vector<int> vst;
		for(int it : st){
			vst.emplace_back(it);
		}
		int currPow = 1;
      	shuffle(vst.begin(),vst.end(),rng);
		while(currPow <= vst.size()/2){
			int size_a = 0, size_b = 0;
			for(int j=0;j<vst.size();j++){
				if(j & currPow){
					for(int it : vec[vst[j]]){
						reqA[size_a++] = it;
					}
				}else{
					for(int it : vec[vst[j]]){
						reqB[size_b++] = it;
					}
				}
			}
			if(query(size_a,size_b,reqA,reqB)){
				break;
			}else{
				currPow <<= 1;
			}
		}
		vector<int> left,right;
		for(int j=0;j<vst.size();j++){
			if(j & currPow){
				for(int it : vec[vst[j]]){
					left.emplace_back(it);
				}
			}else{
				for(int it : vec[vst[j]]){
					right.emplace_back(it);
				}
			}
		}
		int size_a, size_b;
 
		size_b = 0;
		for(int it : right){
			reqB[size_b++] = it;
		}
		while(left.size() > 1){
			int sz = left.size()/2;
			vector<int> vlef,vrig;
			for(int j=0;j<left.size();j++){
				if(j < sz){
					vlef.emplace_back(left[j]);
				}else{
					vrig.emplace_back(left[j]);
				}
			}
			size_a = 0;
			for(int it : vlef){
				reqA[size_a++] = it;
			}
			if(query(size_a,size_b,reqA,reqB)){
				left = vlef;
			}else{
				left = vrig;
			}
		}
 
		size_b = 0;
		for(int it : left){
			reqB[size_b++] = it;
		}
		while(right.size() > 1){
			int sz = right.size()/2;
			vector<int> vlef,vrig;
			for(int j=0;j<right.size();j++){
				if(j < sz){
					vlef.emplace_back(right[j]);
				}else{
					vrig.emplace_back(right[j]);
				}
			}
			size_a = 0;
			for(int it : vlef){
				reqA[size_a++] = it;
			}
			if(query(size_a,size_b,reqA,reqB)){
				right = vlef;
			}else{
				right = vrig;
			}
		}
		setRoad(left.back(),right.back());
		join(left.back(),right.back());
	}
}

Compilation message (stderr)

icc.cpp: In function 'void run(int)':
icc.cpp:32:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   while(currPow <= vst.size()/2){
      |         ~~~~~~~~^~~~~~~~~~~~~~~
icc.cpp:34:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |    for(int j=0;j<vst.size();j++){
      |                ~^~~~~~~~~~~
icc.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int j=0;j<vst.size();j++){
      |               ~^~~~~~~~~~~
icc.cpp:72:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |    for(int j=0;j<left.size();j++){
      |                ~^~~~~~~~~~~~
icc.cpp:97:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |    for(int j=0;j<right.size();j++){
      |                ~^~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10