oj.uz

Submission #1112884

# Submission time Handle Problem Language Result Execution time Memory
1112884 2024-11-15T07:04:43 Z Jawad_Akbar_JJ ICC (CEOI16_icc) C++17
100 / 100
 88 ms 768 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 592 KB Ok! 105 queries used.
2 Correct 5 ms 592 KB Ok! 98 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 592 KB Ok! 518 queries used.
2 Correct 22 ms 760 KB Ok! 486 queries used.
3 Correct 22 ms 592 KB Ok! 499 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 764 KB Ok! 1356 queries used.
2 Correct 67 ms 680 KB Ok! 1187 queries used.
3 Correct 67 ms 592 KB Ok! 1326 queries used.
4 Correct 78 ms 684 KB Ok! 1332 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 592 KB Ok! 1319 queries used.
2 Correct 67 ms 592 KB Ok! 1312 queries used.
3 Correct 73 ms 592 KB Ok! 1269 queries used.
4 Correct 66 ms 768 KB Ok! 1319 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 592 KB Ok! 1274 queries used.
2 Correct 77 ms 684 KB Ok! 1287 queries used.
3 Correct 64 ms 592 KB Ok! 1240 queries used.
4 Correct 66 ms 592 KB Ok! 1296 queries used.
5 Correct 69 ms 688 KB Ok! 1362 queries used.
6 Correct 70 ms 604 KB Ok! 1333 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 592 KB Ok! 1266 queries used.
2 Correct 64 ms 684 KB Ok! 1217 queries used.