Submission #604576

#	Time	Username	Problem	Language	Result	Execution time	Memory
604576		maximath_1	ICC (CEOI16_icc)	C++11	61 / 100	157 ms	508 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
 
const int MX = 1005;
 
int par[MX];
int find(int nw){
	return par[nw] = (par[nw] == nw ? nw : find(par[nw]));
}
mt19937 rng(time(NULL));
void run(int N){
	for(int i = 1; i <= N; i ++)
		par[i] = i;
	for(int times = 1; times < N; times ++){
		vector<int> color(N + 1, -1), lf, rg;
		set<vector<int> > cc;
		int gt = 0;
		do{
			for(int i = 1; i <= N; i ++) if(find(i) == i)
				color[i] = rng() % 2;
			for(int i = 1; i <= N; i ++) color[i] = color[find(i)];
			if(cc.count(color)) continue;
			cc.insert(color);
			lf.clear(); rg.clear();
			for(int i = 1; i <= N; i ++)
				if(color[i]) rg.push_back(i);
				else lf.push_back(i);
			int xl[lf.size()], xr[rg.size()];
			for(int i = 0; i < lf.size(); i ++) xl[i] = lf[i];
			for(int i = 0; i < rg.size(); i ++) xr[i] = rg[i];
			if(lf.empty() || rg.empty()) continue;
			gt = query(lf.size(), rg.size(), xl, xr);
		}while(gt == 0);
 
		int l = 0, r = rg.size() - 1, rs = r + 1;
		for(int md; l <= r;){
			md = (l + r) / 2;
			vector<int> nrg;
			for(int j = 0; j <= md; j ++) nrg.push_back(rg[j]);
			int xl[lf.size()], xr[nrg.size()];
			for(int i = 0; i < lf.size(); i ++) xl[i] = lf[i];
			for(int i = 0; i < nrg.size(); i ++) xr[i] = nrg[i];
			gt = query(lf.size(), nrg.size(), xl, xr);
			if(gt){
				rs = md; r = md - 1;
			}else{
				l = md + 1;
			}
		}
 
		int u = rg[rs]; rg.clear(); rg.push_back(u);
		swap(lf, rg);
 
		l = 0, r = rg.size() - 1, rs = r + 1;
		for(int md; l <= r;){
			md = (l + r) / 2;
			vector<int> nrg;
			for(int j = 0; j <= md; j ++) nrg.push_back(rg[j]);
			int xl[lf.size()], xr[nrg.size()];
			for(int i = 0; i < lf.size(); i ++) xl[i] = lf[i];
			for(int i = 0; i < nrg.size(); i ++) xr[i] = nrg[i];
			gt = query(lf.size(), nrg.size(), xl, xr);
			if(gt){
				rs = md; r = md - 1;
			}else{
				l = md + 1;
			}
		}
 
		int v = rg[rs];
 
		setRoad(u, v);
		u = find(u); v = find(v);
		par[u] = v;
	}
}

Compilation message (stderr)

icc.cpp: In function 'void run(int)':
icc.cpp:30:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    for(int i = 0; i < lf.size(); i ++) xl[i] = lf[i];
      |                   ~~^~~~~~~~~~~
icc.cpp:31:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |    for(int i = 0; i < rg.size(); i ++) xr[i] = rg[i];
      |                   ~~^~~~~~~~~~~
icc.cpp:42:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    for(int i = 0; i < lf.size(); i ++) xl[i] = lf[i];
      |                   ~~^~~~~~~~~~~
icc.cpp:43:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    for(int i = 0; i < nrg.size(); i ++) xr[i] = nrg[i];
      |                   ~~^~~~~~~~~~~~
icc.cpp:61:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |    for(int i = 0; i < lf.size(); i ++) xl[i] = lf[i];
      |                   ~~^~~~~~~~~~~
icc.cpp:62:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |    for(int i = 0; i < nrg.size(); i ++) xr[i] = nrg[i];
      |                   ~~^~~~~~~~~~~~

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