oj.uz

답안 #604887

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
604887 2022-07-25T10:37:11 Z CSQ31 CEOI16_icc (CEOI16_icc) C++17
61 / 100
 226 ms 496 KB 
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
int par[1000];
int find(int x){
	if(x==par[x])return x;
	return par[x] = find(par[x]);
}
void unite(int a,int b){
	a = find(a);
	b = find(b);
	if(a==b)return;
	par[a] = b;
	
}
int n;
int A[200],B[200],an,bn;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
/*
int query(int a, int b, int *A, int *B){
	int ans;
	for(int i=0;i<a;i++)cout<<A[i]<<" ";
	cout<<'\n';
	for(int i=0;i<b;i++)cout<<B[i]<<" ";
	cout<<'\n';
	cin>>ans;
	return ans;
}
void setRoad(int a, int b){
	cout<<"added edge"<<'\n';
	cout<<a<<" "<<b<<'\n';
}*/
void run(int N){
	n = N;
	for(int i=1;i<=n;i++)par[i] = i;
	for(int i=1;i<n;i++){
		vector<int>g;
		vector<vector<int>>p(n+1);
		for(int j=1;j<=n;j++){
			if(j==find(j))g.push_back(j);
			p[find(j)].push_back(j);
		}
		while(true){
			int m = g.size();
			vector<int>f,s;
			for(int i=0;i<m;i++){
				if(uniform_int_distribution<int>(0,1)(rng))f.push_back(g[i]);
				else s.push_back(g[i]);	
			}
			int ptr = 0;
			for(int y:f){
				for(int x:p[y])A[ptr++] = x;
			}
			an = ptr;
			bn = n-ptr;
			ptr = 0;
			for(int y:s){
				for(int x:p[y])B[ptr++] = x;
			}
			if(query(an,bn,A,B))break;
		}
		int cnt = 0;
		int l = 1,r = an;
		while(r>l){
			int mid = (l+r)/2;
			if(query(mid,bn,A,B))r = mid;
			else l = mid+1;
			cnt++;
		}
		int v = A[r-1];
		l = 1;
		r = bn;
		while(r>l){
			int mid = (l+r)/2;
			if(query(an,mid,A,B))r = mid;
			else l = mid+1;
			cnt++;
		}
		assert(cnt<=14);
		int u = B[r-1];
		unite(v,u);
		setRoad(v,u);
	}
	
}
/*
int main()
{
	int m;
	cin>>m;
	run(m);
	
}*/

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 468 KB Ok! 111 queries used.
2 Correct 6 ms 468 KB Ok! 113 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 468 KB Ok! 542 queries used.
2 Correct 52 ms 488 KB Ok! 856 queries used.
3 Correct 51 ms 484 KB Ok! 802 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 492 KB Ok! 1517 queries used.
2 Correct 226 ms 492 KB Ok! 2159 queries used.
3 Correct 200 ms 488 KB Ok! 1751 queries used.
4 Correct 158 ms 488 KB Ok! 1713 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 488 KB Ok! 1562 queries used.
2 Correct 139 ms 492 KB Ok! 1680 queries used.
3 Correct 148 ms 496 KB Ok! 1879 queries used.
4 Correct 135 ms 496 KB Ok! 1634 queries used.

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 151 ms 488 KB Too many queries! 1859 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

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