#include "grader.cpp"
#include <bits/stdc++.h>
#include "park.h"
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) ;
int rand(int l , int r)
{
return uniform_int_distribution<int>(l , r)(rng) ;
}
const int MAX = 1400 + 10 ;
static int Place[MAX] ;
int n ;
int deg[MAX] ;
vector< vector<int> >adj(MAX) ;
int mark[MAX] ;
vector<int>order ;
void dfs(int node)
{
order.push_back(node) ;
for(auto &child : adj[node])
dfs(child) ;
}
bool check(int mid , int node)
{
for(int i = 0 ; i < n ; ++i)
{
if(!mark[i])
Place[i] = 1 ;
else
Place[i] = 0 ;
}
for(int i = 0 ; i <= mid ; ++i)
Place[order[i]] = 1 ;
return Ask(0 , node , Place) ;
}
int Find_Par(int node)
{
int l = 0 , r = (int)(order.size()) - 1 ;
int node2 = 0 ;
while(l <= r)
{
int mid = (l + r) >> 1 ;
if(check(mid , node))
node2 = order[mid] , r = mid-1 ;
else
l = mid+1 ;
}
return node2 ;
}
bool check2(vector<int>&v , int l , int r , int node)
{
for(int i = 0 ; i < n ; ++i)
Place[i] = 1 ;
for(int i = l ; i <= r ; ++i)
Place[v[i]] = 0 ;
return (!Ask(0 , node , Place)) ;
}
bool cmp(int a , int b)
{
for(int i = 0 ; i < n ; ++i)
Place[i] = 1 ;
Place[a] = 0 ;
return (!Ask(0 , b , Place)) ; //if false then a is ancestor b
}
vector<int>Find_Ancestors(int node)
{
vector<int>v ;
for(int i = 0 ; i < n ; ++i)
{
if((!mark[i]) && i != node)
v.push_back(i) ;
}
int prv = -1 ;
vector<int>ancestors ;
for(int i = 0 ; i < v.size() ; ++i)
{
int l = prv+1 , r = (int)(v.size()) - 1 ;
int idx = -1 ;
while(l <= r)
{
int mid = (l + r) >> 1 ;
if(check2(v , prv+1 , mid , node))
idx = mid , r = mid-1 ;
else
l = mid+1 ;
}
if(idx == -1)
break ;
ancestors.push_back(v[idx]) ;
prv = idx ;
}
sort(ancestors.begin() , ancestors.end() , cmp) ;
return ancestors ;
}
void solve(int node)
{
order.clear() ;
dfs(0) ;
int par = Find_Par(node) ;
vector<int>v = Find_Ancestors(node) ;
if(v.size())
{
adj[par].push_back(v[0]) ;
for(int i = 0 ; i+1 < v.size() ; ++i)
adj[v[i]].push_back(v[i+1]) ;
adj[v.back()].push_back(node) ;
for(auto &x : v)
mark[x] = 1 ;
}
else
adj[par].push_back(node) ;
mark[node] = 1 ;
}
void Detect(int T, int N)
{
n = N ;
mark[0] = 1 ;
for(int i = 1 ; i < n ; ++i)
{
if(mark[i])
continue ;
solve(i) ;
}
for(int i = 0 ; i < n ; ++i)
{
for(auto &child : adj[i])
Answer(min(i , child) , max(i , child)) ;
}
return ;
}
Compilation message
park.cpp: In function 'std::vector<int> Find_Ancestors(int)':
park.cpp:88:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int i = 0 ; i < v.size() ; ++i)
| ~~^~~~~~~~~~
park.cpp: In function 'void solve(int)':
park.cpp:118:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for(int i = 0 ; i+1 < v.size() ; ++i)
| ~~~~^~~~~~~~~~
/usr/bin/ld: /tmp/ccHseecd.o: in function `Answer(int, int)':
grader.cpp:(.text+0xd0): multiple definition of `Answer(int, int)'; /tmp/ccNRYaRe.o:park.cpp:(.text+0xd0): first defined here
/usr/bin/ld: /tmp/ccHseecd.o: in function `Ask(int, int, int*)':
grader.cpp:(.text+0x170): multiple definition of `Ask(int, int, int*)'; /tmp/ccNRYaRe.o:park.cpp:(.text+0x170): first defined here
/usr/bin/ld: /tmp/ccHseecd.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccNRYaRe.o:park.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
