Submission #211819

#	Time	Username	Problem	Language	Result	Execution time	Memory
211819		bensonlzl	ICC (CEOI16_icc)	C++14	100 / 100	170 ms	632 KiB

icc

#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef pair<int,int> pi;
 
int s0, s1, a[105], b[105];
 
int par[105];
vector<int> sz[105];
int cnt[8], setbit;
 
void res(){
	for (int i = 0; i < 105; ++i){
		a[i] = b[i] = 0;
	}
	s0 = s1 = 0;
}
 
int query_v(vector<int> A, vector<int> B){
	res();
	for (int i = 0; i < A.size(); ++i){
		a[i] = A[i];
	}
	for (int i = 0; i < B.size(); ++i){
		b[i] = B[i];
	}
	return query(A.size(),B.size(),a,b);
}
 
pi solve(vector<int> A, vector<int> B){
	//cerr << A.size() << ' ' << B.size() << '\n';
	if (B.size() == 1){
		if (A.size() == 1){
			return pi(A[0],B[0]);
		}
		else return solve(B,A);
	}
	vector<int> b0, b1;
	for (int i = 0; i < B.size(); ++i){
		if (i%2 == 0) b0.push_back(B[i]);
		else b1.push_back(B[i]);
	}
	int q = query_v(A,b0);
	if (q) return solve(A,b0);
	else return solve(A,b1);
}
 
int find_par(int x){
	if (par[x] != x) par[x] = find_par(par[x]);
	return par[x];
}
 
void merg(int x, int y){
	int X = find_par(x), Y = find_par(y);
	if (X == Y) return;
	if (sz[X].size() < sz[Y].size()) swap(X,Y);
	for (auto it : sz[Y]){
		sz[X].push_back(it);
	}
	par[Y] = X;
}
 
vector<int> expand(vector<int> p){
	vector<int> r;
	for (auto it : p){
		for (auto it2 : sz[it]){
			r.push_back(it2);
		}
	}
	return r;
}
 
 
 
void run(int n) {
	for (int i = 1; i <= n; ++i){
		par[i] = i;
		sz[i].push_back(i);
	}
    for (int i = 1; i < n; ++i){
    	vector<int> pars;
    	for (int k = 1; k <= n; ++k){
    		pars.push_back(find_par(k));
    	}
    	
    	sort(pars.begin(),pars.end());
    	pars.resize(unique(pars.begin(),pars.end())-pars.begin());
    	vector<int> v0, v1, ax, bx;
    	int check = 0;
    	for (int b = 0; b < 6; ++b){
    		v0.clear();
    		v1.clear();
    		ax.clear();
    		bx.clear();
    		for (int j = 0; j < pars.size(); ++j){
    			if (j & (1 << b)) v1.push_back(pars[j]);
    			else v0.push_back(pars[j]);
    		}
    		ax = expand(v0);
    		bx = expand(v1);
    		int q = query_v(ax,bx);
    		//cerr << b << ' ' << q << '\n';
    		if (q){
    			check = 1;
    			break;
    		}
    		
    	}
    	if (!check){
    		v0.clear();
    		v1.clear();
    		ax.clear();
    		bx.clear();
    		for (int j = 0; j < pars.size(); ++j){
    			if (j & (1 << 6)) v1.push_back(pars[j]);
    			else v0.push_back(pars[j]);
    		}
    		ax = expand(v0);
    		bx = expand(v1);
    	}
    	pi X = solve(ax,bx);
    	//cerr << X.first << ' ' << X.second << '\n';
    	setRoad(X.first,X.second);
    	merg(X.first,X.second);
    }
}

Compilation message (stderr)

icc.cpp: In function 'int query_v(std::vector<int>, std::vector<int>)':
icc.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < A.size(); ++i){
                  ~~^~~~~~~~~~
icc.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < B.size(); ++i){
                  ~~^~~~~~~~~~
icc.cpp: In function 'pi solve(std::vector<int>, std::vector<int>)':
icc.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < B.size(); ++i){
                  ~~^~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:98:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < pars.size(); ++j){
                       ~~^~~~~~~~~~~~~
icc.cpp:117:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < pars.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