Submission #1244527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244527		nvujica	ICC (CEOI16_icc)	C++20	61 / 100	107 ms	632 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"

#define ll long long
#define fi first
#define se second

using namespace std;

const int maxn = 110;

int lena, lenb;
vector <int> comp[maxn];
int par[maxn];
int a[maxn];
int b[maxn];
int bio[maxn];
vector <int> head;
vector <int> va;
vector <int> vb;

//bool query(int f, int g, int h[], int j[]){
//	for(int i = 0; i < lena; i++) cout << a[i] << ' ';
//	cout << ": ";
//	for(int i = 0; i < lenb; i++) cout << b[i] << ' ';	
//	cout << endl;
//	bool odg;
//	cin >> odg;
//	return odg;
//}

//void setRoad(int x, int y){
//	cout << "cesta: " << x << ' ' << y << endl;
//}

void run(int n){
	srand(time(0));
	
	for(int i = 1; i <= n; i++){
		comp[i].push_back(i);
		par[i] = i;
	}
	
	for(int k = n; k >= 2; k--){
		head.clear();
		
		for(int i = 1; i <= n; i++){
			if(par[i] == i) head.push_back(i);
		}
		
		while(true){
			memset(bio, -1, sizeof bio);
			
			int cnt = 0;
			
			while(cnt < k / 2){
				int x = head[rand() % k];
				
				if(bio[x] != -1) continue;
				
//				cout << x << endl;
				
				bio[x] = 1;
				cnt++;
			}
			
			lena = 0;
			lenb = 0;
			
			for(int i = 0; i < k; i++){
				if(bio[head[i]] == 1){
					for(auto x: comp[head[i]]){
						b[lenb] = x;
						lenb++;
					}
				}
				else {
					for(auto x: comp[head[i]]){
						a[lena] = x;
						lena++;
					}
				}
			}
			
			if(query(lena, lenb, a, b) == 1) break;
		}
		
		va.clear();
		vb.clear();
		
//		for(int i = 0; i < lena; i++){
//			for(auto x: comp[a[i]]) va.push_back(x);
//		}
//		
//		for(int i = 0; i < lenb; i++){
//			for(auto x: comp[b[i]]) vb.push_back(x);
//		}
//		
//		for(int i = 0; i < va.size(); i++){
//			a[i] = va[i];
//		}
//		
//		for(int i = 0; i < vb.size(); i++){
//			b[i] = vb[i];
//		}
//		
//		lena = va.size();
//		lenb = vb.size();

		for(int i = 0; i < lena; i++) va.push_back(a[i]);
		for(int i = 0; i < lenb; i++) vb.push_back(b[i]);
		
		int lo = 0, hi = lena - 1;
		while(lo < hi){
			int mid = (lo + hi) / 2;
			
			lena = 0;
			
			for(int i = 0; i <= mid; i++){
				a[lena] = va[i];
				lena++;
			}
			
			if(query(lena, lenb, a, b) == 1) hi = mid;
			else lo = mid + 1;
		}
		
		int x = a[hi];
		
		lena = 1;
		a[0] = x;
		
		lo = 0, hi = lenb - 1;
		while(lo < hi){
			int mid = (lo + hi) / 2;
			
			lenb = 0;
			
			for(int i = 0; i <= mid; i++){
				b[lenb] = vb[i];
				lenb++;
			}
			
			if(query(lena, lenb, a, b) == 1) hi = mid;
			else lo = mid + 1;
		}
		
		int y = b[hi];
		
		setRoad(x, y);
		
		for(auto i: comp[par[y]]){
			par[i] = par[x];
			comp[par[x]].push_back(i);
		}
	}
}


//int main(){
//	int n;
//	cin >> n;
//	
//	run(n);
//	
//	return 0;
//}

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