oj.uz

답안 #605193

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
605193 2022-07-25T13:44:38 Z Drew_ CEOI16_icc (CEOI16_icc) C++17
100 / 100
 513 ms 520 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define f1 first
#define s2 second
 
using ii = pair<int, int>;
 
// int query(int size_a, int size_b, int a[], int b[]);
// void setRoad(int u, int v);
// void WA() { cout << "WA\n"; assert(1); exit(0); }
 
mt19937 RNG(69);
 
const int MAX = 107;
 
int ds[MAX];
inline int frep(int x) { return ds[x] == x ? x : ds[x] = frep(ds[x]); }
inline void join(int x, int y) { ds[frep(x)] = frep(y); }
 
namespace brute
{
	void solve(int N)
	{
		iota(ds+1, ds+N+1, 1);
 
		int a[MAX], b[MAX];
		for (int rep = 0; rep < N-1; ++rep)
		{
			bool ok = false;
			for (int i = 1; i <= N && !ok; ++i)
			{
				for (int j = i+1; j <= N && !ok; ++j)
				{
					if (frep(i) == frep(j))
						continue;
 
					a[0] = i; b[0] = j;
					if (query(1, 1, a, b))
					{
						setRoad(i, j);
						join(i, j);
						ok = true;
					}
				}
			}
		}
	}
}
 
void run(int N)
{
	int ty = -1, qcount = 0;
	const auto split = [&](vector<ii> v) -> pair<vector<ii>, vector<ii>> 
	{
		sort(v.begin(), v.end());
 
		vector<ii> tmp;
		for (auto &[x, y] : v)
		{
			if (!tmp.empty() && x == tmp.back().f1) tmp.back().s2++;
			else tmp.pb({x, 1});
		}
 
		ty = (int)tmp.size();
		
		bitset<MAX> L;
		int dif = 1e9;
		for (int rep = 0; rep < 696; ++rep)
		{
			shuffle(tmp.begin(), tmp.end(), RNG);
 
			int p = 0, q = 0;
			for (auto &[x, y] : tmp)
			{
				if (p > q) q += y;
				else p += y;
			}
 
			if (abs(p-q) < dif)
			{
				dif = abs(p-q);
				p = 0, q = 0; L.reset();
				for (auto &[x, y] : tmp)
				{
					if (p > q) q += y;
					else L[x] = true, p += y;
				}
			}
		}
 
		vector<ii> l, r;
		for (auto &[x, y] : v)
		{
			if (L[x]) l.pb({x, y});
			else r.pb({x, y});
		}
 
		return {l, r};
	};
 
	iota(ds+1, ds+N+1, 1);
 
	int a[MAX], b[MAX];
	for (int rep = 0; rep < N-1; ++rep)
	{
		// cerr << "rep: " << rep << '\n';
 
		// split [1, N] into two groups
		// city `x` must be in the same group with city `frep(x)`
 
		vector<vector<ii>> cur;
		{
			vector<ii> vec;
			for (int i = 1; i <= N; ++i)
				vec.pb({frep(i), i});
			sort(vec.begin(), vec.end());
 
			cur.pb(vec);
		}
 
		for (;;)
		{
			vector<vector<ii>> A, B;
			for (auto vec : cur)
			{
				auto [v1, v2] = split(vec);
				if (ty == 1)
					continue;
				A.pb(v1); B.pb(v2);
			}
			
			// cerr << "vec: ";
			// for (auto vec : cur)
			// {
			// 	for (auto &[x, y] : vec)
			// 		cerr << y << " ";
			// 	cerr << ", ";
			// }
			// cerr << '\n';
 
			int sa = 0, sb  = 0;
			for (auto v : A)
				for (auto [x, y] : v)
					a[sa++] = y;
			for (auto v : B)
				for (auto [x, y] : v)
					b[sb++] = y;
 
			// for (auto [x, y] : v1)
			// 	for (auto [p, q] : v2)
			// 		assert(y != q);
 
			// cerr << "A: ";
			// for (auto vec : A)
			// {
			// 	for (auto &[x, y] : vec)
			// 		cerr << y << " ";
			// 	cerr << ", ";
			// }
			// cerr << '\n';
 
			// cerr << "B: ";
			// for (auto vec : B)
			// {
			// 	for (auto &[x, y] : vec)
			// 		cerr << y << " ";
			// 	cerr << ", ";
			// }
			// cerr << '\n';
 
			// if (++qcount >= 2250) assert(1);
			if (query(sa, sb, a, b))
			{
				vector<ii> v1, v2;
				{
					int l = 0, r = (int)A.size() - 1;
					while (l < r)
					{
						int mid = (l + r) >> 1;
 
						sa = 0;
						for (int i = l; i <= mid; ++i)
							for (auto [x, y] : A[i])
								a[sa++] = y;
 
						for (int i = l; i <= mid; ++i)
							for (auto [x, y] : B[i])
								b[sb++] = y;
 
						if (query(sa, sb, a, b)) r = mid;
						else l = mid + 1;
					}
 
					v1 = A[l], v2 = B[l];
					
					sa = 0;
					for (auto [x, y] : v1)
						a[sa++] = y;
 
					sb = 0;
					for (auto [x, y] : v2)
						b[sb++] = y;
				}
 
				// cerr << "v1: ";
				// for (auto [x, y] : v1)
				// 	cerr << y << " ";
				// cerr << '\n';
 
				// cerr << "v2: ";
				// for (auto [x, y] : v2)
				// 	cerr << y << " ";
				// cerr << '\n';
 
				
				{
					int l = 0, r = (int)v2.size() - 1;
					while (l < r)
					{
						int mid = (l + r) >> 1;
						
						sb = mid-l+1;
						for (int i = l; i <= mid; ++i)
							b[i-l] = v2[i].s2;
 
						// if (++qcount >= 2250) assert(1);
 
						if (query(sa, sb, a, b)) r = mid;
						else l = mid + 1;
					}
					sb = 1; b[0] = v2[l].s2;
				}
 
				{
					int l = 0, r = (int)v1.size() - 1;
					while (l < r)
					{
						int mid = (l + r) >> 1;
 
						sa = mid-l+1;
						for (int i = l; i <= mid; ++i)
							a[i-l] = v1[i].s2;
 
						// if (++qcount >= 2250) assert(1);
 
						if (query(sa, sb, a, b)) r = mid;
						else l = mid + 1;
					}
					sa = 1; a[0] = v1[l].s2;
				}
 
				setRoad(a[0], b[0]);
				join(a[0], b[0]);
				break;
			}
			else
			{
				cur.clear();
				for (auto v : A)
					cur.pb(v);
				for (auto v : B)
					cur.pb(v);
			}
		};
	}
 
	// if (N == 100)
	// {
	// 	assert(1);
	// }
}
 
// int N, cur = 0, QC = 0;
// int U[MAX], V[MAX];
// bitset<MAX> yes[MAX];
 
// void setRoad(int u, int v)
// {
// 	// cerr << "SET ----->> " << u << " and " << v << '\n';
// 	if ((U[cur] == u && V[cur] == v) || (U[cur] == v && V[cur] == u))
// 	{
// 		if (++cur < N-1)
// 			yes[U[cur]][V[cur]] = yes[V[cur]][U[cur]] = true;
// 		return;
// 	}
// 	WA();
// }
 
// int query(int size_a, int size_b, int a[], int b[])
// {
// 	QC++;
// 	for (int i = 0; i < size_a; ++i)
// 		for (int j = 0; j < size_b; ++j)
// 		{
// 			assert(a[i] != b[j]);
// 			if (yes[a[i]][b[j]])
// 				return true;
// 		}
// 	return false;
// }
 
// int main()
// {
// 	ios ::  sync_with_stdio(0);
// 	cin.tie(0);
// 	cout.tie(0);
 
// 	cin >> N;
// 	for (int i = 0; i < N-1; ++i)
// 		cin >> U[i] >> V[i];
 
// 	yes[U[0]][V[0]] = yes[V[0]][U[0]] = true;
// 	run(N);
 
// 	if (cur == N-1) cout << "AC\n";
// 	else cout << "WA\n", assert(1);
 
// 	cout << "query count: " << QC << '\n';
// }

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:55:15: warning: unused variable 'qcount' [-Wunused-variable]
   55 |  int ty = -1, qcount = 0;
      |               ^~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 468 KB Ok! 96 queries used.
2 Correct 7 ms 500 KB Ok! 95 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 492 KB Ok! 503 queries used.
2 Correct 113 ms 492 KB Ok! 432 queries used.
3 Correct 106 ms 492 KB Ok! 453 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 281 ms 500 KB Ok! 1241 queries used.
2 Correct 491 ms 508 KB Ok! 1044 queries used.
3 Correct 241 ms 520 KB Ok! 1177 queries used.
4 Correct 394 ms 512 KB Ok! 1210 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 320 ms 508 KB Ok! 1169 queries used.
2 Correct 403 ms 520 KB Ok! 1193 queries used.
3 Correct 482 ms 508 KB Ok! 1135 queries used.
4 Correct 232 ms 496 KB Ok! 1203 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 492 ms 520 KB Ok! 1128 queries used.
2 Correct 488 ms 508 KB Ok! 1143 queries used.
3 Correct 513 ms 520 KB Ok! 1156 queries used.
4 Correct 473 ms 516 KB Ok! 1184 queries used.
5 Correct 397 ms 504 KB Ok! 1257 queries used.
6 Correct 447 ms 500 KB Ok! 1255 queries used.

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 476 ms 520 KB Ok! 1141 queries used.
2 Correct 497 ms 512 KB Ok! 1078 queries used.