oj.uz

답안 #605150

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
605150 2022-07-25T13:25:11 Z UncoolAnon CEOI16_icc (CEOI16_icc) C++14
100 / 100
 158 ms 1060 KB 
#include "icc.h"
#include <bits/stdc++.h> 
 
 
#define pii pair<int,int> 
#define F first 
#define S second 
#define mp make_pair 
 
using namespace std; 
 
/*int query(int size_a, int size_b, int a[], int b[]){
	cout << "first is : " ; 
	for(int i=0;i<size_a;i++) cout << a[i] << " "; 
	cout << endl; 
	cout << "second is : " ; 
	for(int i=0;i<size_b;i++) cout<<b[i]<< " "; 
	cout<<endl; 
	int x ; 
	cin>>x; 
	return x ; 
}
void setRoad(int a,int b){
	cout <<"! " << a << " " << b << endl ; 
	return ; 
}*/
int query(vector<int> a , vector<int> b){
	int na=a.size(),nb=b.size(); 
	int* arr1 = new int[na];
	for(int i=0;i<na;i++) arr1[i]=a[i]; 
    int* arr2 = new int[nb];
	for(int i=0;i<nb;i++) arr2[i]=b[i]; 
	return query(na,nb,arr1,arr2); 
}
void run(int n) {
	srand(time(0)); 
	vector<int> id,gr[n+1],rid(n+1); 
	for(int i=1;i<=n;i++) {id.push_back(i); gr[i].push_back(i);rid[i]=i;}
	function<void(vector<int>&,vector<int>)> compose=[&](vector<int>& a,vector<int> b){
		for(int&x:b) for(int&node:gr[x]) a.push_back(node); 
		return ; 
	}; 
	for(int i=1;i<n;i++){
		vector<pii> in; 
		in.push_back(mp(0,id.size()-1)); 
		random_shuffle(id.begin(),id.end()); 
		int zez=0; 
		while(1){
			vector<pii> inF,inS;  
			for(pii&x:in){
				inF.push_back(mp(x.F,(x.F+x.S)/2)); 
				inS.push_back(mp((x.F+x.S)/2+1,x.S)); 
			}
			vector<int> a,b; 
			for(int j=0;j<inF.size();j++){
				for(int k=inF[j].F;k<=inF[j].S;k++) compose(a,gr[id[k]]); 
				for(int k=inS[j].F;k<=inS[j].S;k++) compose(b,gr[id[k]]); 
 			}
			if(query(a,b)){
				int l=-1,r=a.size(); 
				while(r-l!=1){
					int md=(r+l)/2; 
					vector<int> tmp; 
					for(int j=0;j<=md;j++) 
						tmp.push_back(a[j]); 
					if(query(tmp,b)) r=md; 
					else l=md; 
				}
				int founda=a[r]; 
				l=-1,r=b.size(); 
				while(r-l!=1){
					int md=(r+l)/2; 
					vector<int> tmp; 
					for(int j=0;j<=md;j++)
						tmp.push_back(b[j]); 
					if(query(a,tmp)) r=md; 
					else l=md; 
				}
				int foundb=b[r]; 
				setRoad(founda,foundb); 
				int kek=-1,lol=-1; 
				for(int j=0;j<id.size();j++)
					if(id[j]==rid[founda]) 
						kek=j; 
					
				for(int j=0;j<id.size();j++)
					if(id[j]==rid[foundb]) 
						lol=j; 
				id.erase(id.begin()+kek); 
				founda=rid[founda]; 
				foundb=rid[foundb]; 
				for(int&x:gr[founda]){
					gr[foundb].push_back(x); 
					rid[x]=foundb; 
				}
				gr[founda].clear(); 
				break; 
			}
			in.clear(); 
			for(pii&x:inF) if(x.F!=x.S) in.push_back(x); 
			for(pii&x:inS) if(x.F!=x.S) in.push_back(x); 
		}
	}
	return ; 
}
/*int main(){
	run(7); 
	return 0; 
}*/

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |    for(int j=0;j<inF.size();j++){
      |                ~^~~~~~~~~~~
icc.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int j=0;j<id.size();j++)
      |                 ~^~~~~~~~~~
icc.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int j=0;j<id.size();j++)
      |                 ~^~~~~~~~~~
icc.cpp:81:16: warning: variable 'lol' set but not used [-Wunused-but-set-variable]
   81 |     int kek=-1,lol=-1;
      |                ^~~
icc.cpp:47:7: warning: unused variable 'zez' [-Wunused-variable]
   47 |   int zez=0;
      |       ^~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 468 KB Ok! 107 queries used.
2 Correct 5 ms 468 KB Ok! 105 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 524 KB Ok! 562 queries used.
2 Correct 50 ms 552 KB Ok! 649 queries used.
3 Correct 38 ms 588 KB Ok! 648 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 139 ms 912 KB Ok! 1456 queries used.
2 Correct 131 ms 868 KB Ok! 1564 queries used.
3 Correct 143 ms 1020 KB Ok! 1585 queries used.
4 Correct 130 ms 968 KB Ok! 1543 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 126 ms 1028 KB Ok! 1530 queries used.
2 Correct 123 ms 924 KB Ok! 1477 queries used.
3 Correct 129 ms 1060 KB Ok! 1583 queries used.
4 Correct 121 ms 916 KB Ok! 1493 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 972 KB Ok! 1599 queries used.
2 Correct 134 ms 956 KB Ok! 1617 queries used.
3 Correct 150 ms 1016 KB Ok! 1621 queries used.
4 Correct 141 ms 968 KB Ok! 1596 queries used.
5 Correct 128 ms 1032 KB Ok! 1518 queries used.
6 Correct 134 ms 1036 KB Ok! 1585 queries used.

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 972 KB Ok! 1609 queries used.
2 Correct 146 ms 932 KB Ok! 1559 queries used.