#include<bits/stdc++.h>
#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;
void Solve(int N)
{
int n=N;
vector<int> M(N);
for(int i = 0; i < N; i++) {
M[i] = 1;
}
if(n==1){
vector<int> vec = {1};
Answer(vec);
return ;
}
int border = -1;
for(int i = 0; i < n ; i++){
M[i] = 0;
int r = Query(M);
if(r==1){
//border
border = i;
break;
}
M[i] = 1;
}
bool in[n];
fill(in,in+n,false);
in[border] = true;
vector<vector<int>> chaines;
int tot = 1;
while(tot<N){
vector<int> chaine;
vector<int> q(n);
fill(q.begin(),q.end(),0);
for(int i = 0;i<n;i++){
if(!in[i]){
q[i] = 1;
if(Query(q)==((int)chaine.size()+1)){
chaine.push_back(i);
tot++;
in[i] = true;
}else{
q[i] = 0;
}
}
}
chaines.push_back(chaine);
}
vector<int> ans;
ans.push_back(border);
vector<int> asking(n);
fill(asking.begin(),asking.end(),0);
asking[border] = 1;
for(int i = 1; i < n ; i ++){
for(int c = 0; c < (int)chaines.size(); c++){
if(chaines[c].size()==0)continue;
int low = 0;
int high = chaines[c].size();
while(low<high){
int mid = (low+high)/2;
for(int i = low ; i <= mid ; i++)
asking[chaines[c][i]] = 1;
int Q = Query(asking);
for(int i = low ; i <= mid ; i++)
asking[chaines[c][i]] = 0;
if(Q==(mid-low+1)){
high = mid;
}else{
low = mid + 1;
}
}
if(low != (int)(chaines[c].size())){
//finded !
int nxt = chaines[c][low];
chaines[c].erase(chaines[c].begin()+low);
ans.push_back(nxt);
asking[nxt] = 1;
break;
}
}
}
for(int i = 0;i<n;i++)ans[i]++;
Answer(ans);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
19 ms |
344 KB |
# of queries: 1859 |
| 2 |
Correct |
18 ms |
344 KB |
# of queries: 1891 |
| 3 |
Correct |
21 ms |
600 KB |
# of queries: 2165 |
| 4 |
Correct |
17 ms |
344 KB |
# of queries: 2102 |
| 5 |
Correct |
14 ms |
340 KB |
# of queries: 1946 |
| 6 |
Correct |
16 ms |
344 KB |
# of queries: 2041 |
| 7 |
Correct |
24 ms |
344 KB |
# of queries: 2079 |
| 8 |
Correct |
17 ms |
344 KB |
# of queries: 1951 |
| 9 |
Correct |
13 ms |
344 KB |
# of queries: 1981 |
| 10 |
Correct |
13 ms |
344 KB |
# of queries: 1180 |
| 11 |
Correct |
1 ms |
344 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
344 KB |
# of queries: 3 |
| 13 |
Correct |
1 ms |
344 KB |
# of queries: 7 |
| 14 |
Correct |
0 ms |
344 KB |
# of queries: 11 |
| 15 |
Correct |
1 ms |
344 KB |
# of queries: 72 |
| 16 |
Correct |
2 ms |
344 KB |
# of queries: 160 |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
19 ms |
344 KB |
# of queries: 1859 |
| 2 |
Correct |
18 ms |
344 KB |
# of queries: 1891 |
| 3 |
Correct |
21 ms |
600 KB |
# of queries: 2165 |
| 4 |
Correct |
17 ms |
344 KB |
# of queries: 2102 |
| 5 |
Correct |
14 ms |
340 KB |
# of queries: 1946 |
| 6 |
Correct |
16 ms |
344 KB |
# of queries: 2041 |
| 7 |
Correct |
24 ms |
344 KB |
# of queries: 2079 |
| 8 |
Correct |
17 ms |
344 KB |
# of queries: 1951 |
| 9 |
Correct |
13 ms |
344 KB |
# of queries: 1981 |
| 10 |
Correct |
13 ms |
344 KB |
# of queries: 1180 |
| 11 |
Correct |
1 ms |
344 KB |
# of queries: 0 |
| 12 |
Correct |
0 ms |
344 KB |
# of queries: 3 |
| 13 |
Correct |
1 ms |
344 KB |
# of queries: 7 |
| 14 |
Correct |
0 ms |
344 KB |
# of queries: 11 |
| 15 |
Correct |
1 ms |
344 KB |
# of queries: 72 |
| 16 |
Correct |
2 ms |
344 KB |
# of queries: 160 |
| 17 |
Correct |
271 ms |
436 KB |
# of queries: 14588 |
| 18 |
Correct |
287 ms |
600 KB |
# of queries: 14037 |
| 19 |
Correct |
284 ms |
844 KB |
# of queries: 13981 |
| 20 |
Correct |
226 ms |
600 KB |
# of queries: 13179 |
| 21 |
Correct |
203 ms |
428 KB |
# of queries: 12375 |
| 22 |
Correct |
269 ms |
428 KB |
# of queries: 14122 |
| 23 |
Correct |
256 ms |
428 KB |
# of queries: 13828 |
| 24 |
Correct |
86 ms |
424 KB |
# of queries: 6201 |
| 25 |
Correct |
236 ms |
592 KB |
# of queries: 13719 |
| 26 |
Correct |
234 ms |
428 KB |
# of queries: 12912 |
| 27 |
Correct |
79 ms |
420 KB |
# of queries: 6513 |
| 28 |
Correct |
237 ms |
432 KB |
# of queries: 12984 |
| 29 |
Correct |
231 ms |
700 KB |
# of queries: 12966 |
| 30 |
Correct |
228 ms |
848 KB |
# of queries: 12984 |
