oj.uz

Submission #608581

# Submission time Handle Problem Language Result Execution time Memory
608581 2022-07-27T08:28:17 Z Mr_Husanboy ICC (CEOI16_icc) C++14
100 / 100
 147 ms 596 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));
		for(auto u:comp) random_shuffle(all(u));
		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();
		}
		random_shuffle(all(comp));
	}
}

Compilation message

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Ok! 102 queries used.
2 Correct 5 ms 468 KB Ok! 96 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 504 KB Ok! 534 queries used.
2 Correct 35 ms 484 KB Ok! 657 queries used.
3 Correct 34 ms 468 KB Ok! 649 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 508 KB Ok! 1407 queries used.
2 Correct 147 ms 492 KB Ok! 1609 queries used.
3 Correct 116 ms 500 KB Ok! 1603 queries used.
4 Correct 104 ms 512 KB Ok! 1472 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 492 KB Ok! 1509 queries used.
2 Correct 116 ms 496 KB Ok! 1464 queries used.
3 Correct 120 ms 488 KB Ok! 1599 queries used.
4 Correct 107 ms 468 KB Ok! 1479 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 492 KB Ok! 1599 queries used.
2 Correct 127 ms 488 KB Ok! 1606 queries used.
3 Correct 120 ms 496 KB Ok! 1628 queries used.
4 Correct 113 ms 504 KB Ok! 1589 queries used.
5 Correct 106 ms 504 KB Ok! 1462 queries used.
6 Correct 106 ms 468 KB Ok! 1537 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 596 KB Ok! 1601 queries used.
2 Correct 116 ms 468 KB Ok! 1618 queries used.