#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() (rand() >> 3)*rand()
//void setRoad(int a, int b);
//int query(int x, int y, int a[], int b[]);
/*void setRoad(int x, int y){cout << "*" << x << ' ' << y << endl;}
bool query(int x, int y, vector<int> v, vector<int> w){
fox(l, x) cout << v[l] << ' '; cout << endl;
fox(l, y) cout << w[l] << ' '; cout << endl;
int ans;
cin >> ans;
return ans;
};*/
int x, y, n, a[105], b[105];
vector<int> v, w, u;
vector<vector<int> > com;
bool query2(int x, int y, vector<int> V, vector<int> W){
vector<int> t1, t2;
t1=t2=vector<int>();
fox(l, x){
fox(l2, com[v[l]].size()) t1.pb(com[v[l]][l2]);
}
fox(l, y){
fox(l2, com[w[l]].size()) t2.pb(com[w[l]][l2]);
}
fox(l, t1.size()) a[l]=t1[l];
fox(l, t2.size()) b[l]=t2[l];
return query(t1.size(), t2.size(), a, b);
}
bool query3(int x, int y, vector<int> V, vector<int> W){
fox(l, x) a[l]=V[l];
fox(l, y) b[l]=W[l];
return query(x, y, a, b);
}
void solve(){
vector<int> t1, t2;
t1=t2=vector<int>();
fox(l, v.size()){
fox(l2, com[v[l]].size()) t1.pb(com[v[l]][l2]);
}
fox(l, w.size()){
fox(l2, com[w[l]].size()) t2.pb(com[w[l]][l2]);
}
v=t1; w=t2;
int lo=0, mid, hi=v.size()-1;
while(lo<hi){
mid=(lo+hi)/2;
u.clear();
fox(l, mid+1) u.pb(v[l]);
if (query3(mid+1, w.size(), u, w)){
hi=mid;
} else {
lo=mid+1;
}
}
x=v[lo];
lo=0; hi=w.size()-1;
while(lo<hi){
mid=(lo+hi)/2;
u.clear();
fox(l, mid+1) u.pb(w[l]);
if (query3(v.size(), mid+1, v, u)){
hi=mid;
} else {
lo=mid+1;
}
}
y=w[lo];
}
void get(){
for (int b=1; ; b*=3){
v.clear();
w.clear();
fox1(l, n){
if (b&l) v.pb(l);
else w.pb(l);
}
//cout << b << endl;
if (query2(v.size(), w.size(), v, w)){
solve();
//cout << b << endl;
return;
}
}
}
int find_comp(int x){
fox(l, com.size()){
fox(l2, com[l].size()){
if (com[l][l2]==x){
return l;
}
}
}
}
void run(int N){
n=N;
fox(l, n+2) com.pb(vector<int>(1, l));
/*fox(l, N){
v.pb(vector<int>(1, l+1));
}*/
fox(l, N-1){
get();
setRoad(x, y);
x=find_comp(x);
y=find_comp(y);
fox(l, com[y].size()){
com[x].pb(com[y][l]);
}
com.erase(com.begin()+y);
--n;
/*fox1(l, n){
fox(l2, com[l].size()){
cout<< com[l][l2] << ' ';
}
cout << endl;
} cout << endl;*/
}
}
/*int main(){
run(4);
return 0;
}*/
Compilation message
icc.cpp: In function 'bool query2(int, int, std::vector<int>, std::vector<int>)':
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define fox(k, x) for (int k=0; k<x; ++k)
^
icc.cpp:45:9: note: in expansion of macro 'fox'
fox(l2, com[v[l]].size()) t1.pb(com[v[l]][l2]);
^
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define fox(k, x) for (int k=0; k<x; ++k)
^
icc.cpp:48:9: note: in expansion of macro 'fox'
fox(l2, com[w[l]].size()) t2.pb(com[w[l]][l2]);
^
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define fox(k, x) for (int k=0; k<x; ++k)
^
icc.cpp:50:5: note: in expansion of macro 'fox'
fox(l, t1.size()) a[l]=t1[l];
^
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define fox(k, x) for (int k=0; k<x; ++k)
^
icc.cpp:51:5: note: in expansion of macro 'fox'
fox(l, t2.size()) b[l]=t2[l];
^
icc.cpp: In function 'void solve()':
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define fox(k, x) for (int k=0; k<x; ++k)
^
icc.cpp:62:5: note: in expansion of macro 'fox'
fox(l, v.size()){
^
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define fox(k, x) for (int k=0; k<x; ++k)
^
icc.cpp:63:9: note: in expansion of macro 'fox'
fox(l2, com[v[l]].size()) t1.pb(com[v[l]][l2]);
^
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define fox(k, x) for (int k=0; k<x; ++k)
^
icc.cpp:65:5: note: in expansion of macro 'fox'
fox(l, w.size()){
^
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define fox(k, x) for (int k=0; k<x; ++k)
^
icc.cpp:66:9: note: in expansion of macro 'fox'
fox(l2, com[w[l]].size()) t2.pb(com[w[l]][l2]);
^
icc.cpp: In function 'int find_comp(int)':
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define fox(k, x) for (int k=0; k<x; ++k)
^
icc.cpp:111:9: note: in expansion of macro 'fox'
fox(l, com.size()){
^
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define fox(k, x) for (int k=0; k<x; ++k)
^
icc.cpp:112:13: note: in expansion of macro 'fox'
fox(l2, com[l].size()){
^
icc.cpp: In function 'void run(int)':
icc.cpp:19:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define fox(k, x) for (int k=0; k<x; ++k)
^
icc.cpp:130:9: note: in expansion of macro 'fox'
fox(l, com[y].size()){
^
icc.cpp: In function 'int find_comp(int)':
icc.cpp:118:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
166 ms |
2084 KB |
Number of queries more than 3000 out of 1500 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
336 ms |
2080 KB |
Number of queries more than 5000 out of 2500 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
369 ms |
2084 KB |
Number of queries more than 4500 out of 2250 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
336 ms |
2084 KB |
Number of queries more than 4000 out of 2000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
296 ms |
2084 KB |
Number of queries more than 3550 out of 1775 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
263 ms |
2084 KB |
Number of queries more than 3250 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
