oj.uz

Submission #608564

# Submission time Handle Problem Language Result Execution time Memory
608564 2022-07-27T08:22:13 Z Mr_Husanboy ICC (CEOI16_icc) C++14
90 / 100
 155 ms 588 KB 
#include<bits/stdc++.h>


#include "icc.h"
 
 
using namespace std;
using ll = long long;


 
mt19937 rng(123);
#define ld long double
#define ull unsigned long long 
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(a) a.begin(), a.end()
#define ff first
#define ss second
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define setp(x) setprecision(x)


const int mod=1e9+7;
int inf=1e9;
const int LOGN = 20;
const int MXX=3e5;
int mx = 10007 ;
int n,k;


vector<vi> g;
vector<int> con, vis;


int nodef(vector<int> A, vector<int> B){
	int l = 0, r = A.size()-1;
	while(l < r){
		int m = (l + r) / 2;
		vector<int> tem;
		for(int i=l; i<=m; i++){
			tem.push_back(A[i]);
		}
		if(query(tem.size(),B.size(), tem.data(), B.data())){
			r = m;
		}else l = m+1;
	}
	return A[r];
}

void dfs(int a, int par = -1){
	con.push_back(a);
	vis[a] = 1;
	for(auto u:g[a]){
		if(u == par) continue;
		dfs(u, a);
	}
}

void run(int n){
	g.resize(n+5);
	vector<vi> comp;
	for(int i=1; i<=n; i++) comp.push_back(vi{i});
	
	for(int I = 0; I < n-1; I ++){
		random_shuffle(all(comp));
		vis.assign(n+1, 0);
		for(int LOG = 0; (1<<LOG) <comp.size(); LOG ++){
			vector<int> A, B;
			for(int i = 0; i < comp.size(); i++){
				if(i & (1 << LOG)){
					for(auto u : comp[i]) A.push_back(u);
				}else{
					for(auto u : comp[i]) B.push_back(u);
				}
			}
			if(query(A.size(), B.size(), A.data(), B.data()) == 0){
				continue;
			}
		//	cout << "A: "; for(auto u : A) cout << u << ' '; cout << endl << "B: "; for(auto u : B) cout << u << ' '; cout << endl;
			int node1 = nodef(A,B);
			int node2 = nodef(B,A);
			setRoad(node1, node2);
			g[node1].push_back(node2);
			g[node2].push_back(node1);
			break;
		}
		comp.clear();
		for(int i=1; i<=n; i++){
			if(vis[i]) continue;
			dfs(i);
			comp.push_back(con);
			con.clear();
		}
	}
}

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:71:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for(int LOG = 0; (1<<LOG) <comp.size(); LOG ++){
      |                    ~~~~~~~~~^~~~~~~~~~~~
icc.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |    for(int i = 0; i < comp.size(); i++){
      |                   ~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Ok! 101 queries used.
2 Correct 5 ms 504 KB Ok! 97 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 468 KB Ok! 528 queries used.
2 Correct 38 ms 484 KB Ok! 654 queries used.
3 Correct 39 ms 488 KB Ok! 645 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 504 KB Ok! 1396 queries used.
2 Correct 125 ms 504 KB Ok! 1613 queries used.
3 Correct 124 ms 508 KB Ok! 1601 queries used.
4 Correct 114 ms 468 KB Ok! 1507 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 492 KB Ok! 1435 queries used.
2 Correct 129 ms 516 KB Ok! 1448 queries used.
3 Correct 126 ms 468 KB Ok! 1632 queries used.
4 Correct 126 ms 508 KB Ok! 1471 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 468 KB Ok! 1609 queries used.
2 Correct 125 ms 500 KB Ok! 1586 queries used.
3 Correct 126 ms 588 KB Ok! 1621 queries used.
4 Correct 139 ms 500 KB Ok! 1585 queries used.
5 Correct 109 ms 432 KB Ok! 1425 queries used.
6 Correct 115 ms 504 KB Ok! 1534 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 120 ms 468 KB Too many queries! 1626 out of 1625
2 Halted 0 ms 0 KB -