#include "park.h"
#include <cstdlib>
#include <vector>
using namespace std;
static int place[1400];
int nNodes;
void clear()
{
for(int j=0;j<nNodes;j++)
place[j] = 0;
}
void fill()
{
for(int j=0;j<nNodes;j++)
place[j] = 1;
}
void ansEdge(int a,int b)
{
if(a>b) swap(a,b);
Answer(a,b);
}
int question(int a,int b,int p[])
{
if(a>b) swap(a,b);
return Ask(a,b,p);
}
void solveRange(int l,int r,vector<int> lst)
{
if(lst.size()==0)
{
ansEdge(l,r);
return;
}
int mid = lst[rand()%lst.size()];
vector<int> lList,rList;
for(int j=0;j<lst.size();j++) if(lst[j]!=mid)
{
fill();
place[lst[j]] = 0;
if(question(l,mid,place)) rList.push_back(lst[j]);
else lList.push_back(lst[j]);
}
solveRange(l,mid,lList);
solveRange(mid,r,rList);
}
vector<int> d[10];
int seen[1400];
int depth[1400];
void Detect(int T,int N)
{
nNodes = N;
if(T==1)
{
for(int i=0;i<N;i++)
for(int j=i+1;j<N;j++)
{
clear();
place[i] = place[j] = 1;
if(Ask(i,j,place))
ansEdge(i,j);
}
}
if(T==2)
{
vector<int> lst;
for(int i=1;i<N-1;i++)
lst.push_back(i);
solveRange(0,N-1,lst);
}
if(T==3)
{
d[0].push_back(0);
seen[0] = 1;
depth[0] = 0;
for(int k=1;k<10;k++)
{
for(int i=0;i<N;i++) if(seen[i]==0)
{
clear();
for(int j=0;j<N;j++)
if(seen[j]==1)
place[j] = 1;
place[i] = 1;
if(question(0,i,place))
seen[i] = 2;
}
for(int i=0;i<N;i++)
if(seen[i]==2)
{
d[k].push_back(i);
seen[i] = 1;
depth[i] = k;
}
}
for(int i=1;i<N;i++)
{
int k = depth[i]-1;
if(k==0)
{
ansEdge(0,i);
continue;
}
int low = 0;
int high = d[k].size()-1;
while(low != high)
{
int mid = (low+high)/2;
clear();
for(int j=0;j<N;j++) if(depth[j]<k) place[j] = 1;
for(int j=low;j<=mid;j++) place[d[k][j]] = 1;
place[i] = 1;
if(question(0,i,place)) high = mid;
else low = mid+1;
}
ansEdge(d[k][low],i);
}
}
}
Compilation message
park.cpp: In function 'void solveRange(int, int, std::vector<int>)':
park.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<lst.size();j++) if(lst[j]!=mid)
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
2044 KB |
Output is correct |
2 |
Correct |
9 ms |
2044 KB |
Output is correct |
3 |
Correct |
9 ms |
2044 KB |
Output is correct |
4 |
Correct |
9 ms |
2044 KB |
Output is correct |
5 |
Correct |
9 ms |
2044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
199 ms |
2176 KB |
Output is correct |
2 |
Correct |
129 ms |
2176 KB |
Output is correct |
3 |
Correct |
133 ms |
2176 KB |
Output is correct |
4 |
Correct |
169 ms |
2044 KB |
Output is correct |
5 |
Correct |
216 ms |
2176 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
173 ms |
2044 KB |
Output is correct |
2 |
Correct |
193 ms |
2044 KB |
Output is correct |
3 |
Correct |
196 ms |
2044 KB |
Output is correct |
4 |
Correct |
129 ms |
2044 KB |
Output is correct |
5 |
Correct |
186 ms |
2044 KB |
Output is correct |
6 |
Correct |
179 ms |
2044 KB |
Output is correct |
7 |
Correct |
143 ms |
2044 KB |
Output is correct |
8 |
Correct |
189 ms |
2044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
2044 KB |
Wrong Answer[6] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
2044 KB |
Wrong Answer[6] |
2 |
Halted |
0 ms |
0 KB |
- |