#include <bits/stdc++.h>
#include "icc.h"
#define N 105
using namespace std;
vector<int> adj[N];
vector<int> x;
bool vis[N];
int qu = 1625;
void dfs(int v){
vis[v] = 1;
x.push_back(v);
for(auto u:adj[v]){
if(!vis[u]){
dfs(u);
}
}
}
/*
void setRoad(int a,int b){
cout <<"ROAD: " << a << " " << b << endl;
return;
}
int query(int sa,int sb,int a[],int b[]){
for(int i=0;i<sa;i++){
cout << a[i] << " ";
}
cout << endl;
for(int i=0;i<sb;i++){
cout << b[i] << " ";
}
cout << endl;
int ret;
cin >> ret;
return ret;
}*/
void solve2(vector<int> l,vector<int> r){
if(l.size() == 1 && r.size() == 1){
setRoad(l[0],r[0]);
adj[l[0]].push_back(r[0]);
adj[r[0]].push_back(l[0]);
return;
}
if(l.size() == 1){
vector<int> a,b;
for(int i=0;i<(int)(r.size()+1)/2;i++){
a.push_back(r[i]);
}
for(int i=(r.size()+1)/2;i<(int)r.size();i++){
b.push_back(r[i]);
}
int sum1 = 1,sum2 = a.size();
int al[sum1],ar[sum2];
al[0] = l[0];
for(int i = 0;i<(int)sum2;i++){
ar[i] = a[i];
}
qu--;
assert(qu >= 0);
if(query(sum1,sum2,al,ar)){
solve2(l,a);
}
else solve2(l,b);
}
else{
vector<int> a,b;
for(int i=0;i<(int)(l.size()+1)/2;i++){
a.push_back(l[i]);
}
for(int i=(l.size()+1)/2;i<(int)l.size();i++){
b.push_back(l[i]);
}
int sum1 = a.size(),sum2 = r.size();
int al[sum1],ar[sum2];
for(int i = 0;i<(int)sum1;i++){
al[i] = a[i];
}
for(int i = 0;i<(int)sum2;i++){
ar[i] = r[i];
}
qu--;
assert(qu >= 0);
if(query(sum1,sum2,al,ar)){
solve2(a,r);
}
else solve2(b,r);
}
}
void go(vector<vector<vector<int>>> a,vector<vector<vector<int>>> b){
vector<int> l,r;
for(auto u:a){
for(auto c:u){
for(auto d:c)
l.push_back(d);
}
}
for(auto u:b){
for(auto c:u){
for(auto d:c)
r.push_back(d);
}
}
solve2(l,r);
}
void solve(vector<vector<int>> tmp){
vector<vector<vector<int>>> v;
v.push_back(tmp);
while(1){
vector<vector<vector<int>>> a,b;
int sum1 = 0;
int sum2 = 0;
for(auto comps:v){
vector<vector<int>> l,r;
for(int i=0;i<(int)comps.size()/2;i++){
l.push_back(comps[i]);
sum1 += comps[i].size();
}
for(int i=comps.size()/2;i<(int)comps.size();i++){
r.push_back(comps[i]);
sum2 += comps[i].size();
}
a.push_back(l);
b.push_back(r);
}
int l[sum1],r[sum2];
int cnt = 0;
for(auto u:a){
for(auto c:u){
for(auto d:c){
l[cnt++] = d;
}
}
}
cnt = 0;
for(auto u:b){
for(auto c:u){
for(auto d:c){
r[cnt++] = d;
}
}
}
qu--;
assert(qu >= 0);
if(query(sum1,sum2,l,r)){
go(a,b);
return;
}
v = a;
for(auto u:b)v.push_back(u);
}
}
void run(int n){
srand(time(NULL));
for(int i = 1;i<n;i++){
vector<vector<int>> comps;
for(int j=1;j<=n;j++){
vis[j] = 0;
}
for(int j=1;j<=n;j++){
if(!vis[j]){
x.clear();
dfs(j);
comps.push_back(x);
}
}
solve(comps);
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
432 KB |
Ok! 94 queries used. |
| 2 |
Correct |
6 ms |
468 KB |
Ok! 98 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
37 ms |
580 KB |
Ok! 554 queries used. |
| 2 |
Correct |
32 ms |
584 KB |
Ok! 596 queries used. |
| 3 |
Correct |
46 ms |
588 KB |
Ok! 595 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
98 ms |
568 KB |
Ok! 1397 queries used. |
| 2 |
Correct |
113 ms |
636 KB |
Ok! 1472 queries used. |
| 3 |
Correct |
116 ms |
640 KB |
Ok! 1545 queries used. |
| 4 |
Correct |
107 ms |
736 KB |
Ok! 1488 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
116 ms |
640 KB |
Ok! 1399 queries used. |
| 2 |
Correct |
111 ms |
624 KB |
Ok! 1501 queries used. |
| 3 |
Correct |
108 ms |
640 KB |
Ok! 1520 queries used. |
| 4 |
Correct |
102 ms |
576 KB |
Ok! 1483 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
147 ms |
568 KB |
Ok! 1494 queries used. |
| 2 |
Correct |
111 ms |
632 KB |
Ok! 1475 queries used. |
| 3 |
Correct |
121 ms |
568 KB |
Ok! 1528 queries used. |
| 4 |
Correct |
118 ms |
608 KB |
Ok! 1536 queries used. |
| 5 |
Correct |
113 ms |
572 KB |
Ok! 1489 queries used. |
| 6 |
Correct |
109 ms |
576 KB |
Ok! 1550 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
119 ms |
636 KB |
Ok! 1523 queries used. |
| 2 |
Correct |
110 ms |
636 KB |
Ok! 1472 queries used. |
