oj.uz

Submission #606600

# Submission time Handle Problem Language Result Execution time Memory
606600 2022-07-26T07:22:52 Z MetalPower ICC (CEOI16_icc) C++14
100 / 100
 127 ms 588 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Ok! 112 queries used.
2 Correct 6 ms 468 KB Ok! 108 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 468 KB Ok! 612 queries used.
2 Correct 27 ms 508 KB Ok! 450 queries used.
3 Correct 31 ms 468 KB Ok! 487 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 468 KB Ok! 1539 queries used.
2 Correct 94 ms 588 KB Ok! 1088 queries used.
3 Correct 101 ms 484 KB Ok! 1524 queries used.
4 Correct 97 ms 484 KB Ok! 1486 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 480 KB Ok! 1435 queries used.
2 Correct 117 ms 496 KB Ok! 1470 queries used.
3 Correct 98 ms 480 KB Ok! 1481 queries used.
4 Correct 99 ms 480 KB Ok! 1505 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 484 KB Ok! 1485 queries used.
2 Correct 99 ms 468 KB Ok! 1450 queries used.
3 Correct 91 ms 480 KB Ok! 1316 queries used.
4 Correct 94 ms 468 KB Ok! 1447 queries used.
5 Correct 105 ms 488 KB Ok! 1518 queries used.
6 Correct 107 ms 484 KB Ok! 1529 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 484 KB Ok! 1438 queries used.
2 Correct 88 ms 480 KB Ok! 1174 queries used.