답안 #605016

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
605016 2022-07-25T12:17:32 Z UncoolAnon CEOI16_icc (CEOI16_icc) C++17
0 / 100
1 ms 852 KB
#include <bits/stdc++.h> 

#include "icc.h"

#define pii pair<int,int> 
#define F first 
#define S second 
#define mp make_pair 
#define endl '\n'

using namespace std; 

#define n_l '\n'
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; cout << to_string(__VA_ARGS__) << endl
template <typename T, size_t N> int SIZE(const T (&t)[N]){ return N; } template<typename T> int SIZE(const T &t){ return t.size(); } string to_string(const string s, int x1=0, int x2=1e9){ return '"' + ((x1 < s.size()) ? s.substr(x1, x2-x1+1) : "") + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(const bool b) { return (b ? "true" : "false"); } string to_string(const char c){ return string({c}); } template<size_t N> string to_string(const bitset<N> &b, int x1=0, int x2=1e9){ string t = ""; for(int __iii__ = min(x1,SIZE(b)),  __jjj__ = min(x2, SIZE(b)-1); __iii__ <= __jjj__; ++__iii__){ t += b[__iii__] + '0'; } return '"' + t + '"'; } template <typename A, typename... C> string to_string(const A (&v), int x1=0, int x2=1e9, C... coords); int l_v_l_v_l = 0, t_a_b_s = 0; template <typename A, typename B> string to_string(const pair<A, B> &p) { l_v_l_v_l++; string res = "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; l_v_l_v_l--; return res; } template <typename A, typename... C> string to_string(const A (&v), int x1, int x2, C... coords) { int rnk = rank<A>::value; string tab(t_a_b_s, ' '); string res = ""; bool first = true; if(l_v_l_v_l == 0) res += n_l; res += tab + "["; x1 = min(x1, SIZE(v)), x2 = min(x2, SIZE(v)); auto l = begin(v); advance(l, x1); auto r = l; advance(r, (x2-x1) + (x2 < SIZE(v))); for (auto e = l; e != r; e = next(e)) { if (!first) { res += ", "; } first = false; l_v_l_v_l++; if(e != l){ if(rnk > 1) { res += n_l; t_a_b_s = l_v_l_v_l; }; } else{ t_a_b_s = 0; } res += to_string(*e, coords...); l_v_l_v_l--; } res += "]"; if(l_v_l_v_l == 0) res += n_l; return res; } void dbgm(){;} template<typename Heads, typename... Tails> void dbgm(Heads H, Tails... T){ cout << to_string(H) << " | "; dbgm(T...); } 
#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgm(__VA_ARGS__); cout << endl
 /*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[1];
	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)); 
		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); 
		}
	}
}

Compilation message

icc.cpp: In function 'std::string to_string(std::string, int, int)':
icc.cpp:15:208: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | template <typename T, size_t N> int SIZE(const T (&t)[N]){ return N; } template<typename T> int SIZE(const T &t){ return t.size(); } string to_string(const string s, int x1=0, int x2=1e9){ return '"' + ((x1 < s.size()) ? s.substr(x1, x2-x1+1) : "") + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(const bool b) { return (b ? "true" : "false"); } string to_string(const char c){ return string({c}); } template<size_t N> string to_string(const bitset<N> &b, int x1=0, int x2=1e9){ string t = ""; for(int __iii__ = min(x1,SIZE(b)),  __jjj__ = min(x2, SIZE(b)-1); __iii__ <= __jjj__; ++__iii__){ t += b[__iii__] + '0'; } return '"' + t + '"'; } template <typename A, typename... C> string to_string(const A (&v), int x1=0, int x2=1e9, C... coords); int l_v_l_v_l = 0, t_a_b_s = 0; template <typename A, typename B> string to_string(const pair<A, B> &p) { l_v_l_v_l++; string res = "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; l_v_l_v_l--; return res; } template <typename A, typename... C> string to_string(const A (&v), int x1, int x2, C... coords) { int rnk = rank<A>::value; string tab(t_a_b_s, ' '); string res = ""; bool first = true; if(l_v_l_v_l == 0) res += n_l; res += tab + "["; x1 = min(x1, SIZE(v)), x2 = min(x2, SIZE(v)); auto l = begin(v); advance(l, x1); auto r = l; advance(r, (x2-x1) + (x2 < SIZE(v))); for (auto e = l; e != r; e = next(e)) { if (!first) { res += ", "; } first = false; l_v_l_v_l++; if(e != l){ if(rnk > 1) { res += n_l; t_a_b_s = l_v_l_v_l; }; } else{ t_a_b_s = 0; } res += to_string(*e, coords...); l_v_l_v_l--; } res += "]"; if(l_v_l_v_l == 0) res += n_l; return res; } void dbgm(){;} template<typename Heads, typename... Tails> void dbgm(Heads H, Tails... T){ cout << to_string(H) << " | "; dbgm(T...); }
      |                                                                                                                                                                                                             ~~~^~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:57: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]
   57 |    for(int j=0;j<inF.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:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int j=0;j<id.size();j++)
      |                 ~^~~~~~~~~~
icc.cpp:83:16: warning: variable 'lol' set but not used [-Wunused-but-set-variable]
   83 |     int kek=-1,lol=-1;
      |                ^~~
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 724 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 724 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 852 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 852 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 852 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 852 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -