oj.uz

답안 #605069

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
605069 2022-07-25T12:42:40 Z UncoolAnon CEOI16_icc (CEOI16_icc) C++14
90 / 100
 124 ms 1116 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) {
	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)); 
		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:53: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]
   53 |    for(int j=0;j<inF.size();j++){
      |                ~^~~~~~~~~~~
icc.cpp:80:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int j=0;j<id.size();j++)
      |                 ~^~~~~~~~~~
icc.cpp:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int j=0;j<id.size();j++)
      |                 ~^~~~~~~~~~
icc.cpp:79:16: warning: variable 'lol' set but not used [-Wunused-but-set-variable]
   79 |     int kek=-1,lol=-1;
      |                ^~~
icc.cpp:45:7: warning: unused variable 'zez' [-Wunused-variable]
   45 |   int zez=0;
      |       ^~~

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 500 KB Ok! 555 queries used.
2 Correct 31 ms 536 KB Ok! 622 queries used.
3 Correct 33 ms 524 KB Ok! 651 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 972 KB Ok! 1478 queries used.
2 Correct 124 ms 900 KB Ok! 1531 queries used.
3 Correct 106 ms 972 KB Ok! 1544 queries used.
4 Correct 121 ms 1116 KB Ok! 1588 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 1000 KB Ok! 1611 queries used.
2 Correct 113 ms 1076 KB Ok! 1565 queries used.
3 Correct 119 ms 1008 KB Ok! 1623 queries used.
4 Correct 117 ms 1024 KB Ok! 1578 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 1016 KB Ok! 1632 queries used.
2 Correct 115 ms 1032 KB Ok! 1602 queries used.
3 Correct 124 ms 1072 KB Ok! 1619 queries used.
4 Correct 117 ms 1040 KB Ok! 1637 queries used.
5 Correct 112 ms 972 KB Ok! 1554 queries used.
6 Correct 117 ms 1112 KB Ok! 1641 queries used.

Subtask #6
0 / 10.0

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