///
/// You fell for it, fool!
/// Thunder Cross Split Attack!
///
#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
typedef long long ll;
using namespace std;
#include "library.h"
const int N = 1010;
int n;
vector<int> v;
int cnt[N];
int adj[N][2];
int mp[N];
int qry2(int x, vector<int>& v, int k)
{
vector<int> kooft(n);
Loop(i,0,k) kooft[v[i]] = 1;
kooft[x] = 1;
return Query(kooft);
}
int getsize(vector<int>& v, int k)
{
int ans = k;
Loop(i,0,k) Loop(j,i+1,k)
if(adj[v[i]][0] == v[j] || adj[v[i]][1] == v[j])
--ans;
return ans;
}
void add(int x)
{
cnt[x]++;
v[x] = 1;
vector<int> can;
Loop(y,0,n) if(y != x && cnt[y] > 0 && cnt[y] < 3)
{
can.push_back(y);
}
for(int _ = 0; _ < 2 && can.size(); ++_)
{
int l = 0, r = can.size();
if(qry2(x,can,r) > getsize(can,r)) break;
while(r-l > 1)
{
int m = (l+r)/2;
if(qry2(x,can,m) <= getsize(can,m)) r = m;
else l = m;
}
int y = can[l];
adj[y][cnt[y]++-1] = x;
adj[x][cnt[x]++-1] = y;
can.erase(can.begin()+l);
}
}
void make(int v, int p, vector<int>& ans)
{
ans.push_back(v+1);
if(adj[v][0] == p)
{if(cnt[v] == 3) make(adj[v][1], v, ans);}
else
make(adj[v][0], v, ans);
}
void Solve(int _n)
{
n = _n;
v.resize(n);
if(n==1){v[0] = 1; Answer(v); return;}
srand(time(0));
vector<int> josuke(n);
iota(josuke.begin(), josuke.end(), 0);
random_shuffle(josuke.begin(),josuke.end());
for(int x : josuke) add(x);
vector<int> ans;
Loop(i,0,n) if(cnt[i] == 2)
{make(i,-1,ans); break;}
Answer(ans);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
21 ms |
200 KB |
# of queries: 1381 |
| 2 |
Correct |
23 ms |
200 KB |
# of queries: 1374 |
| 3 |
Correct |
18 ms |
200 KB |
# of queries: 1465 |
| 4 |
Correct |
21 ms |
200 KB |
# of queries: 1448 |
| 5 |
Correct |
22 ms |
200 KB |
# of queries: 1457 |
| 6 |
Correct |
21 ms |
200 KB |
# of queries: 1460 |
| 7 |
Correct |
26 ms |
200 KB |
# of queries: 1422 |
| 8 |
Correct |
24 ms |
200 KB |
# of queries: 1384 |
| 9 |
Correct |
18 ms |
200 KB |
# of queries: 1451 |
| 10 |
Correct |
12 ms |
200 KB |
# of queries: 842 |
| 11 |
Correct |
0 ms |
200 KB |
# of queries: 0 |
| 12 |
Correct |
1 ms |
300 KB |
# of queries: 1 |
| 13 |
Correct |
0 ms |
200 KB |
# of queries: 4 |
| 14 |
Correct |
0 ms |
200 KB |
# of queries: 7 |
| 15 |
Correct |
1 ms |
296 KB |
# of queries: 59 |
| 16 |
Correct |
1 ms |
304 KB |
# of queries: 122 |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
21 ms |
200 KB |
# of queries: 1381 |
| 2 |
Correct |
23 ms |
200 KB |
# of queries: 1374 |
| 3 |
Correct |
18 ms |
200 KB |
# of queries: 1465 |
| 4 |
Correct |
21 ms |
200 KB |
# of queries: 1448 |
| 5 |
Correct |
22 ms |
200 KB |
# of queries: 1457 |
| 6 |
Correct |
21 ms |
200 KB |
# of queries: 1460 |
| 7 |
Correct |
26 ms |
200 KB |
# of queries: 1422 |
| 8 |
Correct |
24 ms |
200 KB |
# of queries: 1384 |
| 9 |
Correct |
18 ms |
200 KB |
# of queries: 1451 |
| 10 |
Correct |
12 ms |
200 KB |
# of queries: 842 |
| 11 |
Correct |
0 ms |
200 KB |
# of queries: 0 |
| 12 |
Correct |
1 ms |
300 KB |
# of queries: 1 |
| 13 |
Correct |
0 ms |
200 KB |
# of queries: 4 |
| 14 |
Correct |
0 ms |
200 KB |
# of queries: 7 |
| 15 |
Correct |
1 ms |
296 KB |
# of queries: 59 |
| 16 |
Correct |
1 ms |
304 KB |
# of queries: 122 |
| 17 |
Correct |
295 ms |
324 KB |
# of queries: 9521 |
| 18 |
Correct |
304 ms |
200 KB |
# of queries: 9436 |
| 19 |
Correct |
285 ms |
200 KB |
# of queries: 9567 |
| 20 |
Correct |
242 ms |
200 KB |
# of queries: 8922 |
| 21 |
Correct |
238 ms |
200 KB |
# of queries: 8398 |
| 22 |
Correct |
314 ms |
200 KB |
# of queries: 9566 |
| 23 |
Correct |
308 ms |
200 KB |
# of queries: 9538 |
| 24 |
Correct |
89 ms |
304 KB |
# of queries: 4432 |
| 25 |
Correct |
285 ms |
308 KB |
# of queries: 9321 |
| 26 |
Correct |
257 ms |
328 KB |
# of queries: 8713 |
| 27 |
Correct |
84 ms |
200 KB |
# of queries: 4415 |
| 28 |
Correct |
315 ms |
200 KB |
# of queries: 9552 |
| 29 |
Correct |
329 ms |
200 KB |
# of queries: 9543 |
| 30 |
Correct |
282 ms |
200 KB |
# of queries: 9578 |
