Submission #115231

#	Time	Username	Problem	Language	Result	Execution time	Memory
115231		sebinkim	ICC (CEOI16_icc)	C++14	100 / 100	155 ms	760 KiB

icc

#include <bits/stdc++.h>

#include "icc.h"

using namespace std;

vector <int> V[111], Z;
int P[111], K[111];
int X[111], Y[111];
int x, y;

int find(int p) { return p == P[p]? p : P[p] = find(P[p]); }
void unite(int p, int q) { P[find(p)] = find(q); }

void run(int n)
{
	int i, j, k, t, b, m, s, e, u, v, p, q;
	
	for(i=0; i<n; i++){
		P[i] = i;
	}
	
	for(i=1; i<n; i++){
		for(j=0; j<n; j++){
			V[j].clear();
		}
		
		for(j=0, k=0; j<n; j++){
			if(find(j) == j) K[k ++] = j;
			V[find(j)].push_back(j);
		}
		
		for(t=0, b=0; (1 << t) < k; t++){
			x = 0, y = 0;
			for(j=0; j<k; j++){
				if(j & (1 << t)){
					for(int &v: V[K[j]]) X[x ++] = v + 1;
				}
				else{
					for(int &v: V[K[j]]) Y[y ++] = v + 1;
				}
			}
			
			if(query(x, y, X, Y)){
				b |= 1 << t;
			}
		}
		
		Z.clear();
		
		for(j=0; j<k; j++){
			if((j ^ b) < k && j < (j ^ b)){
				Z.push_back(j);
			}
		}
		
		for(s=0, e=Z.size()-2; s<=e; ){
			m = s + e >> 1;
			x = 0; y = 0;
			for(j=0; j<=m; j++){
				for(int &v: V[K[Z[j]]]) X[x ++] = v + 1;
				for(int &v: V[K[Z[j] ^ b]]) Y[y ++] = v + 1;
			}
			if(query(x, y, X, Y)) e = m - 1;
			else s = m + 1;
		}
		
		p = K[Z[e + 1]]; q = K[Z[e + 1] ^ b];
		
		y = 0;
		for(int &v: V[q]) Y[y ++] = v + 1;
		
		for(s=0, e=V[p].size()-2; s<=e; ){
			m = s + e >> 1;
			x = 0;
			for(j=0; j<=m; j++){
				X[x ++] = V[p][j] + 1;
			}
			if(query(x, y, X, Y)) e = m - 1;
			else s = m + 1;
		}
		
		u = V[p][e + 1];
		
		y = 0;
		for(int &v: V[p]) Y[y ++] = v + 1;
		
		for(s=0, e=V[q].size()-2; s<=e; ){
			m = s + e >> 1;
			x = 0;
			for(j=0; j<=m; j++){
				X[x ++] = V[q][j] + 1;
			}
			if(query(x, y, X, Y)) e = m - 1;
			else s = m + 1;
		}
		
		v = V[q][e + 1];
		
		setRoad(u + 1, v + 1);
		unite(u, v);
	}
}

Compilation message (stderr)

icc.cpp: In function 'void run(int)':
icc.cpp:58:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    m = s + e >> 1;
        ~~^~~
icc.cpp:74:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    m = s + e >> 1;
        ~~^~~
icc.cpp:89:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    m = s + e >> 1;
        ~~^~~

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