#include "park.h"
#include <bits/stdc++.h>
#define ll int
#define ld long double
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
const ll maxn = 1405;
static int Place[1400];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random(ll l ,ll r)
{
ll x = rng();
return (abs(x)%(r-l+1)+l);
}
ll t, n;
vector<pll> Edge;
ll par[maxn];
ll find_par(ll v)
{
if(v==par[v]) return v;
else return par[v] = find_par(par[v]);
}
bool mid(ll a, ll b, ll c)
{
if(a>c) swap(a, c);
//cout << a << " " << b << " " << c << "\n";
for(int i = 0; i< n; i++) Place[i] = 1;
Place[b] = 0;
return !Ask(a, c, Place);
}
bool adj(ll a, ll b)
{
if(a>b) swap(a, b);
//cout << a << " " << b << "\n";
for(int i = 0; i< n; i++) Place[i] = 0;
Place[a] = Place[b] = 1;
return Ask(a, b, Place);
}
vector<ll> solve(vector<ll> &A)
{
if(A.size()==1)
{
vector<ll> X;
X.push_back(A[0]);
return X;
}
else if(A.size()==2)
{
Edge.push_back(mp(A[0], A[1]));
vector<ll> X;
X.push_back(A[0]);
X.push_back(A[1]);
return X;
}
vector<vector<ll>> T;
swap(A[0], A[random(0, A.size()-1)]);
if(A.size()==5)
{
for(int i = 0; i< A.size(); i++)
{
if(A[i]==0) swap(A[i], A[0]);
}
}
//random_shuffle(A.begin(), A.end());
//for(auto u: A) cout << u << " ";
//cout << "\n-1 " << A[0] << "\n";
ll root = A[0];
for(int i = 1; i< A.size(); i++)
{
for(int j = 0; j<= T.size(); j++)
{
if(j==T.size())
{
T.emplace_back();
T[T.size()-1].push_back(A[i]);
break;
}
else
{
if(mid(T[j][0], root, A[i])) continue;
else
{
T[j].push_back(A[i]);
break;
}
}
}
}
vector<ll> save;
for(int i = 0; i< T.size(); i++)
{
vector<ll> ss = solve(T[i]);
ll value = -1;
for(auto u: ss)
{
//cout << root << " " << u << "\n";
if(adj(u, root))
{
value = u;
Edge.push_back(mp(u, root));
break;
}
}
for(auto u: ss)
{
if(u==value&&T[i].size()!=1) continue;
save.push_back(u);
}
}
save.clear();
return save;
}
void Detect(int xaa, int xa) {
t = xaa; n = xa;
vector<ll> T;
for(int i = 0; i< n; i++) T.push_back(i);
T = solve(T);
//cout << Edge.size() << "\n";
for(auto u: Edge)
{
if(u.fi>u.se) swap(u.fi, u.se);
//cout << u.fi << " " << u.se << "\n";
Answer(u.fi, u.se);
}
}
Compilation message
park.cpp: In function 'std::vector<int> solve(std::vector<int>&)':
park.cpp:63:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i = 0; i< A.size(); i++)
| ~^~~~~~~~~~
park.cpp:72:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int i = 1; i< A.size(); i++)
| ~^~~~~~~~~~
park.cpp:74:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int j = 0; j<= T.size(); j++)
| ~^~~~~~~~~~~
park.cpp:76:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | if(j==T.size())
| ~^~~~~~~~~~
park.cpp:94:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(int i = 0; i< T.size(); i++)
| ~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Wrong Answer[2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
252 ms |
580 KB |
Wrong Answer[6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
918 ms |
636 KB |
Wrong Answer[5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
649 ms |
592 KB |
Wrong Answer[5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1024 ms |
720 KB |
Wrong Answer[5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
