oj.uz

Submission #104286

# Submission time Handle Problem Language Result Execution time Memory
104286 2019-04-04T17:53:44 Z tmk ICC (CEOI16_icc) C++17
100 / 100
 128 ms 660 KB 
#include<bits/stdc++.h>
#include "icc.h"
using namespace std;
#ifndef d
#define d(...)
#endif
#define st first
#define nd second
#define pb push_back
#define siz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
typedef long long LL;
typedef long double LD;
constexpr int INF=1e9+7;
constexpr LL INFL=1e18;
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

constexpr int maxn = 105;

using Component = vector<int>;

int n;
vector<Component> C;

vector<int> get_vertices(vector<int>& ind) {
	vector<int> ret;
	for(auto i:ind)
		for(auto x:C[i])
			ret.push_back(x);
	return ret;
}

int make_query(vector<int> l, vector<int> r) {
	return query(l.size(), r.size(), l.data(), r.data());
}

void merge(int a, int b) {
	auto f = [&](int x) {
		for(size_t i=0; i<C.size(); i++)
			if(find(all(C[i]), x) != C[i].end())
				return i;
		return C.size();
	};
	
	a = f(a), b = f(b);
	for(auto x:C[b])
		C[a].push_back(x);
	C[b] = C.back();
	C.pop_back();
}

void run(int _n) {
	n = _n;
	for(int i=1; i<=n; i++) {
		C.push_back({i});
	}
	
	mt19937 rng(time(0));
	for(int _=0; _<n-1; _++) {
		vector<int> L, R, ind(C.size());
		iota(all(ind), 0);
		shuffle(all(ind), rng);
		vector<pair<int, int>> segs = {{0, C.size()}};
		while(true) {
			vector<pair<int, int>> tmp;
			L.clear(), R.clear();
			for(auto& e:segs) {
				if(e.st + 1 == e.nd) continue;
				int s = (e.st + e.nd) / 2;
				for(int i=e.st; i<s; i++)
					L.push_back(i);
				for(int i=s; i<e.nd; i++)
					R.push_back(i);
				tmp.emplace_back(e.st, s);
				tmp.emplace_back(s, e.nd);
			}
			
			if(make_query(get_vertices(L), get_vertices(R))) break;
			else segs = tmp;
		}		
		
		L = get_vertices(L);
		R = get_vertices(R);
		
		auto it = L.begin(), it2 = L.end();
		while(it + 1 != it2) {
			auto s = it + distance(it, it2) / 2;
			if(make_query(vector<int>(it, s), R))
				it2 = s;
			else
				it = s;
		}
		
		int a = *it;
		
		it = R.begin(), it2 = R.end();
		while(it + 1 != it2) {
			auto s = it + distance(it, it2) / 2;
			if(make_query(vector<int>(it, s), L))
				it2 = s;
			else
				it = s;
		}
		
		int b = *it;
		
		setRoad(a, b);
		merge(a, b);
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 512 KB Ok! 101 queries used.
2 Correct 8 ms 512 KB Ok! 98 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 568 KB Ok! 550 queries used.
2 Correct 62 ms 512 KB Ok! 637 queries used.
3 Correct 43 ms 512 KB Ok! 642 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 572 KB Ok! 1567 queries used.
2 Correct 128 ms 568 KB Ok! 1584 queries used.
3 Correct 123 ms 576 KB Ok! 1612 queries used.
4 Correct 122 ms 512 KB Ok! 1575 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 512 KB Ok! 1576 queries used.
2 Correct 112 ms 660 KB Ok! 1584 queries used.
3 Correct 118 ms 632 KB Ok! 1584 queries used.
4 Correct 111 ms 512 KB Ok! 1556 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 512 KB Ok! 1588 queries used.
2 Correct 124 ms 604 KB Ok! 1589 queries used.
3 Correct 118 ms 580 KB Ok! 1597 queries used.
4 Correct 114 ms 572 KB Ok! 1611 queries used.
5 Correct 113 ms 512 KB Ok! 1595 queries used.
6 Correct 118 ms 632 KB Ok! 1581 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 568 KB Ok! 1589 queries used.
2 Correct 122 ms 576 KB Ok! 1584 queries used.