oj.uz

답안 #546025

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
546025 2022-04-06T04:42:44 Z blue CEOI16_icc (CEOI16_icc) C++17
90 / 100
 228 ms 756 KB 
#include "icc.h"
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
#include <random>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
#define sz(x) int(x.size())

const int mx = 100;

int getRandom(int a, int b)
{
	return a + (rand() % (b-a+1));
}

int vquery(vi A, vi B)
{
	int a[mx], b[mx];
	for(int ai = 0; ai < sz(A); ai++)
		a[ai] = A[ai];

	for(int bi = 0; bi < sz(B); bi++)
		b[bi] = B[bi];

	if(sz(A) == 0 || sz(B) == 0)
		return 0;

	return query(sz(A), sz(B), a, b);
}

void run(int N)
{
	srand(3);

	vi edge[1+N];

	for(int e = 1; e <= N-1; e++)
	{
		cerr << "\n\n\n\n\n";
		cerr << "e = " << e << '\n';
		vi cc(1+N, -1);
		int ccc = 0;

		for(int i = 1; i <= N; i++)
		{
			if(cc[i] != -1) continue;
			ccc++;

			queue<int> tbv;
			tbv.push(i);

			while(!tbv.empty())
			{
				int u = tbv.front();
				tbv.pop();

				cc[u] = ccc - 1;

				cerr << u << " <> " << ccc << '\n';

				for(int v : edge[u])
				{
					if(cc[v] != -1) continue;
					tbv.push(v);
				}
			}
		}

		for(int i = 1; i <= N; i++) cerr << cc[i] << ' ';
			cerr << '\n';

		int k = 0;
		while((1<<k) < N)
			k++;

		vi bits;
		for(int v = 0; v < k; v++)
			bits.push_back(v);

		for(int t = 0; t < 2'000; t++)
		{
			int p = getRandom(0, k-1);
			int q = getRandom(0, k-1);
			if(getRandom(0, 1))
				swap(bits[p], bits[q]);
		}

		int goodbit;
		vi S[2];

		for(int b : bits)
		{

			cerr << "b = " << b << '\n';

			vi s[2];
			for(int i = 1; i <= N; i++)
				s[bool(cc[i] & (1 << b))].push_back(i);

			if(vquery(s[0], s[1]))
			{
				goodbit = b;
				S[0] = s[0];
				S[1] = s[1];
				break;
			}
		}

		while(sz(S[0]) > 1)
		{
			vi SS[2];
			for(int i = 0; i < sz(S[0])/2; i++)
				SS[0].push_back(S[0][i]);
			for(int i = sz(S[0])/2; i < sz(S[0]); i++)
				SS[1].push_back(S[0][i]);

			if(vquery(SS[0], S[1]))
				S[0] = SS[0];
			else
				S[0] = SS[1];
		}

		while(sz(S[1]) > 1)
		{
			vi SS[2];
			for(int i = 0; i < sz(S[1])/2; i++)
				SS[0].push_back(S[1][i]);
			for(int i = sz(S[1])/2; i < sz(S[1]); i++)
				SS[1].push_back(S[1][i]);

			if(vquery(SS[0], S[0]))
				S[1] = SS[0];
			else
				S[1] = SS[1];
		}
		
		int u = S[0][0], v = S[1][0];
		setRoad(u, v);
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
}

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:92:7: warning: variable 'goodbit' set but not used [-Wunused-but-set-variable]
   92 |   int goodbit;
      |       ^~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 468 KB Ok! 100 queries used.
2 Correct 7 ms 468 KB Ok! 103 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 504 KB Ok! 546 queries used.
2 Correct 57 ms 496 KB Ok! 684 queries used.
3 Correct 56 ms 500 KB Ok! 683 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 184 ms 640 KB Ok! 1470 queries used.
2 Correct 190 ms 680 KB Ok! 1680 queries used.
3 Correct 192 ms 756 KB Ok! 1577 queries used.
4 Correct 188 ms 516 KB Ok! 1549 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 588 KB Ok! 1579 queries used.
2 Correct 191 ms 640 KB Ok! 1574 queries used.
3 Correct 191 ms 588 KB Ok! 1641 queries used.
4 Correct 182 ms 588 KB Ok! 1506 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 228 ms 664 KB Ok! 1627 queries used.
2 Correct 203 ms 520 KB Ok! 1634 queries used.
3 Correct 199 ms 516 KB Ok! 1638 queries used.
4 Correct 200 ms 676 KB Ok! 1625 queries used.
5 Correct 178 ms 612 KB Ok! 1541 queries used.
6 Correct 188 ms 532 KB Ok! 1577 queries used.

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 204 ms 664 KB Too many queries! 1629 out of 1625
2 Halted 0 ms 0 KB -