Submission #606600

#	Time	Username	Problem	Language	Result	Execution time	Memory
606600		MetalPower	ICC (CEOI16_icc)	C++14	100 / 100	127 ms	588 KiB

icc

#include <bits/stdc++.h>
using namespace std;

#include "icc.h"

/*
int query(int size_a, int size_b, int a[], int b[]){
	cout << "Query := \n";
	for(int i = 0; i < size_a; i++) cout << a[i] << " ";
	cout << '\n';
	for(int i = 0; i < size_b; i++) cout << b[i] << " ";
	cout << '\n';
	int nans; cin >> nans;
	return nans;
}

void setRoad(int a, int b){
	cout << "Road " << a << " " << b << '\n';
}
*/

const int MX = 105;

int a[MX], b[MX], cc[MX], rep[MX];
vector<int> comp[MX];

int Query(vector<int>& A, vector<int>& B){
	int size_a = A.size(), size_b = B.size();
	for(int i = 0; i < size_a; i++) a[i] = A[i];
	for(int i = 0; i < size_b; i++) b[i] = B[i];
	return query(size_a, size_b, a, b);
}

bool optimal(vector<int>& lf, vector<int>& rg){
	return (int) lf.size() < (int) rg.size();
}

void run(int N){

	// Default components
	for(int i = 1; i <= N; i++) comp[i].push_back(i);

	for(int tc = 1; tc < N; tc++){ // update tc-th edge

		int vxor = 0, vl = 0;

		{
			// Step 1 : Index connected components, split queries by bit

			int cnt = 0;
			for(int i = 1; i <= N; i++){
				if(comp[i].size() == 0) continue;
				rep[cnt] = i;
				for(int nd : comp[i]) cc[nd] = cnt;
				cnt++;
			}

			for(int bit = 1; bit < cnt; bit <<= 1){
				vector<int> lf, rg;
				for(int i = 1; i <= N; i++){
					if(cc[i] & bit) rg.push_back(i);
					else lf.push_back(i);
				}
				if(Query(lf, rg)) vl = bit, vxor ^= bit;
			}
		}

		int lnode = -1, rnode = -1, lcomp = -1, rcomp = -1;

		{
			// Step 2 : Find one side connected component

			vector<int> lf, rg;
			for(int i = 1; i <= N; i++){
				if(cc[i] & vl) rg.push_back(i);
				else lf.push_back(i);
			}

			if(optimal(lf, rg)){ // left is more optimal
				int l = 0, r = (int) lf.size() - 1;
				while(l < r){
					int mid = l + r >> 1; vector<int> vec;
					for(int i = l; i <= mid; i++) vec.push_back(lf[i]);
					if(Query(vec, rg)) r = mid;
					else l = mid + 1;
				}
				lnode = lf[l], lcomp = cc[lnode];
			}else{
				int l = 0, r = (int) rg.size() - 1;
				while(l < r){
					int mid = l + r >> 1; vector<int> vec;
					for(int i = l; i <= mid; i++) vec.push_back(rg[i]);
					if(Query(lf, vec)) r = mid;
					else l = mid + 1;
				}
				rnode = rg[l], rcomp = cc[rnode];
			}

			if(lnode == -1){
				lcomp = vxor ^ rcomp;

				vector<int> rn, vec;
				for(int i = 1; i <= N; i++)
					if(cc[i] == lcomp) vec.push_back(i);
				rn.push_back(rnode);

				int l = 0, r = (int) vec.size() - 1;
				while(l < r){
					int mid = l + r >> 1; vector<int> nvec;
					for(int i = l; i <= mid; i++) nvec.push_back(vec[i]);
					if(Query(nvec, rn)) r = mid;
					else l = mid + 1;
				}
				lnode = vec[l];
			}else{
				rcomp = vxor ^ lcomp;

				vector<int> ln, vec;
				for(int i = 1; i <= N; i++)
					if(cc[i] == rcomp) vec.push_back(i);
				ln.push_back(lnode);

				int l = 0, r = (int) vec.size() - 1;
				while(l < r){
					int mid = l + r >> 1; vector<int> nvec;
					for(int i = l; i <= mid; i++) nvec.push_back(vec[i]);
					if(Query(ln, nvec)) r = mid;
					else l = mid + 1;
				}
				rnode = vec[l];
			}
		}

		setRoad(lnode, rnode);
		for(int nd : comp[rep[rcomp]]) comp[rep[lcomp]].push_back(nd);
		comp[rep[rcomp]].clear();
	}
}

/*
int main(){
	int N; cin >> N;
	run(N);
}
*/

Compilation message (stderr)

icc.cpp: In function 'void run(int)':
icc.cpp:82:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |      int mid = l + r >> 1; vector<int> vec;
      |                ~~^~~
icc.cpp:91:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |      int mid = l + r >> 1; vector<int> vec;
      |                ~~^~~
icc.cpp:109:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |      int mid = l + r >> 1; vector<int> nvec;
      |                ~~^~~
icc.cpp:125:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  125 |      int mid = l + r >> 1; vector<int> nvec;
      |                ~~^~~

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