Submission #1112884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112884		Jawad_Akbar_JJ	ICC (CEOI16_icc)	C++17	100 / 100	88 ms	768 KiB

icc

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include "icc.h"

using namespace std;
set<int> rt;
vector<int> Vec[105];
int Root[105], seen[105][105];

vector<int> get(vector<int> a){
	vector<int> ans;
	for (int i : a)
		for (int j : Vec[i])
			ans.push_back(j);
	return ans;
}

bool Query(vector<int> a,vector<int> b){
	int n1 = a.size(), n2 = b.size();
	return query(n1, n2, &a[0], &b[0]);
}

void solve2(vector<int> lft, vector<int> rgt){
	lft = get(lft);
	int l = 0, r = lft.size();
	while (l + 1 < r){
		int m = (l + r) / 2;
		vector<int> vec2;
		
		for (int i = l;i < m;i++)
			vec2.push_back(lft[i]);
		
		if (Query(vec2, get(rgt)))
			r = m;
		else
			l = m;
	}

	vector<int> v;
	for (int i : rgt)
		if (!seen[Root[lft[l]]][i])
			v.push_back(i);
	rgt = get(v);

	int l2 = 0, r2 = rgt.size();

	while (l2 + 1 < r2){
		int m2 = (l2 + r2) / 2;
		vector<int> vec2;
		for (int i=l2;i<m2;i++)
			vec2.push_back(rgt[i]);

		if (Query({lft[l]}, vec2))
			r2 = m2;
		else
			l2 = m2;
	}

	int A = lft[l], B = rgt[l2];

	setRoad(A, B);
	A = Root[A], B = Root[B];

	for (int i : Vec[B])
		Root[i] = A, Vec[A].push_back(i);
	rt.erase(B);
}

void solve(int n){
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			seen[i][j] = 0;

	vector<int> V;
	for (int i : rt)
		V.push_back(i);
	random_shuffle(begin(V), end(V));
	for (int p=(1<<20);p >= 1;p /= 2){
		if (p >= V.size())
			continue;
		vector<int> lft, rgt;
		for (int j=0, l = 0;j<V.size();j++){
			if (j % p == 0)
				l = 1 - l;
			if (l)
				lft.push_back(V[j]);
			else
				rgt.push_back(V[j]);
		}

		if (p == 1 or Query(get(lft), get(rgt))){
			solve2(lft, rgt);
			return ;
		}
		for (int i : lft)
			for (int j : rgt)
				seen[i][j] = seen[j][i] = 1;
	}
}

void run(int n){
	for (int i=1;i<=n;i++){
		Root[i] = i;
		Vec[i].push_back(i);
		rt.insert(i);
	}
	for (int i=1;i<n;i++)
		solve(n);
}

// int main(){

// }

Compilation message (stderr)

icc.cpp: In function 'void solve(int)':
icc.cpp:81:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   if (p >= V.size())
      |       ~~^~~~~~~~~~~
icc.cpp:84:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for (int j=0, l = 0;j<V.size();j++){
      |                       ~^~~~~~~~~

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