| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 54763 | spencercompton | Park (JOI17_park) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "park.h"
#include <bits/stdc++.h>
using namespace std;
bool in[1400];
static int place[1400];
vector<int> post;
vector<int> adj[1400];
vector<bool> v;
int n;
void dfs(int now){
v[now] = true;
post.push_back(now);
for(int i = 0; i<adj[now].size(); i++){
int to = adj[now][i];
if(!v[to]){
dfs(to);
}
}
}
void from(int a, int b){
if(b<a){
swap(a,b);
}
// cout << "FROM " << a << " " << b << endl;
for(int i = 0; i<n; i++){
place[i] = 0;
}
place[a] = 1;
place[b] = 1;
// cout << "P1 " << a << " " << b << endl;
// for(int i = 0; i<n; i++){
// cout << place[i] << " " ;
// }
// cout << endl;
if(Ask(a,b,place)==1){
// cout << "OK " << endl;
Answer(a,b);
in[a] = true;
in[b] = true;
adj[a].push_back(b);
adj[b].push_back(a);
return;
}
// cout << "NOPE " << endl;
vector<int> outside;
for(int i = 0; i<n; i++){
if(!in[i] && i!=a && i!=b){
outside.push_back(i);
}
}
int low = 0;
int high = (int)outside.size()-1;
while(low<high){
int mid = (low+high)/2;
for(int i = 0; i<n; i++){
place[i] = 1;
}
for(int i = 0; i<=mid; i++){
place[outside[i]] = 1;
}
for(int i = mid+1; i<(int)outside.size(); i++){
place[outside[i]] = 0;
}
if(Ask(a,b,place)==1){
high = mid;
}
else{
low = mid+1;
}
}
from(a,outside[low]);
from(outside[low],b);
}
void Detect(int T, int N)
if(T==1){
for(int i = 0; i<N; i++){
place[i] = 0;
}
for(int i = 0; i<N; i++){
for(int j = i+1; j<N; j++){
place[i] = 1;
place[j] = 1;
if(Ask(i,j,place)==1){
Answer(i,j);
}
place[i] = 0;
place[j] = 0;
}
}
return;
}
if(T==5){
return;
}
n = N;
for(int i = 0; i<N; i++){
place[i] = 0;
}
for(int i = 0; i<N; i++){
in[i] = false;
}
in[0] = true;
for(int i = 1; i<N; i++){
// cout << "X " << i << " " << N << endl;
if(in[i]){
continue;
}
v.clear();
v.resize(N);
post.clear();
dfs(0);
vector<int> possible;
for(int j = 0; j<post.size(); j++){
possible.push_back(post[j]);
}
// cout << "A " << endl;
// for(int j = 0; j<(int)possible.size(); j++){
// cout << possible[j] << " " ;
// }
// cout << "B "<< endl;
while(possible.size()>1){
vector<int> a;
vector<int> b;
for(int j = 0; j<N; j++){
place[j] = 1;
}
for(int j = 0; j<(int)possible.size()/2; j++){
a.push_back(possible[j]);
}
for(int j = (int)possible.size()/2; j<(int)possible.size(); j++){
b.push_back(possible[j]);
place[possible[j]] = 0;
}
// cout << "BEF " << endl;
// for(int j = 0; j<a.size(); j++){
// cout << a[j] << " ";
// }
// cout << endl;
// for(int j = 0; j<b.size(); j++){
// cout << b[j] << " ";
// }
// cout << endl;
// for(int j = 0; j<N; j++){
// cout << place[j] << " ";
// }
// cout << endl;
int xx = a[0];
int yy = i;
if(xx>yy){
swap(xx,yy);
}
if(Ask(xx,yy,place)==1){
possible = a;
}
else{
possible = b;
}
// cout << "AFT " << endl;
}
assert((int)possible.size()==1);
from(possible[0],i);
}
}