| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 594565 |
2022-07-12T16:55:09 Z |
Koosha_mv |
Park (JOI17_park) |
C++14 |
|
119 ms |
780 KB |
#include "park.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
const int N=1505;
mt19937 rng(time(nullptr));
int n,mark[N],place[N];
vector<int> g[N];
void reset(){
f(i,0,n) place[i]=0;
}
int rand(int l,int r){
uniform_int_distribution<int> rnd(l,r-1);
return rnd(rng);
}
int ask(int s,int t){
if(s>t) swap(s,t);
int res=Ask(s,t,place);
return res;
}
void path(int s,int t,vector<int> vec){
if(vec.size()==0){
if(s>t) swap(s,t);
Answer(s,t);
g[s].pb(t);
g[t].pb(s);
return ;
}
int id=vec[rand(0,vec.size())];
reset();
place[s]=place[t]=1;
for(auto x : vec){
place[x]=1;
}
vector<int> L,R;
for(auto x : vec){
if(x==id) continue ;
place[x]=0;
if(ask(s,id)==0) L.pb(x);
else R.pb(x);
place[x]=1;
}
path(s,id,L);
path(id,t,R);
}
void dfs1(int u,int p,vector<int> &vec){
vec.pb(u);
for(auto v : g[u]){
if(v==p) continue ;
dfs1(v,u,vec);
}
}
void Detect(int T, int _n) {
n=_n;
mark[0]=1;
vector<int> B(1);
f(i,1,n){
if(mark[i]) continue ;
vector<int> vec,A;
mark[i]=1;
f(j,0,n) if(!mark[j]) A.pb(j);
int l=-1,r=A.size();
while(1){
while(l+1<r){
int mid=(l+r)>>1;
reset();
place[0]=place[i]=1;
f(j,0,mid) place[A[j]]=1;
f(j,mid,A.size()) place[A[j]]=mark[A[j]];
if(ask(0,i)==0){
l=mid;
}
else{
r=mid;
}
//cout<<l<<" "<<r<<endl;
}
if(l==-1) break;
mark[A[l]]=1;
vec.pb(A[l]);
r=l,l=-1;
}
reset();
vector<int> p;
dfs1(0,0,p);
place[i]=1;
for(auto x : vec) place[x]=1;
l=0,r=p.size();
while(l+1<r){
int mid=(l+r)>>1;
f(j,0,p.size()) place[p[j]]=(j<mid);
if(ask(0,i)==0) l=mid;
else r=mid;
}
//cout<<endl<<i<<" -> "<<endl;
//eror(p[l]);
//dbgv(p);
//dbgv(vec);
path(p[l],i,vec);
}
}
/*
1
5 4
0 3
3 4
3 1
0 2
*/
Compilation message
park.cpp: In function 'void Detect(int, int)':
park.cpp:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | #define f(i,a,b) for(int i=a;i<b;i++)
......
91 | f(j,mid,A.size()) place[A[j]]=mark[A[j]];
| ~~~~~~~~~~~~~~
park.cpp:91:5: note: in expansion of macro 'f'
91 | f(j,mid,A.size()) place[A[j]]=mark[A[j]];
| ^
park.cpp:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | #define f(i,a,b) for(int i=a;i<b;i++)
......
113 | f(j,0,p.size()) place[p[j]]=(j<mid);
| ~~~~~~~~~~~~
park.cpp:113:4: note: in expansion of macro 'f'
113 | f(j,0,p.size()) place[p[j]]=(j<mid);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Wrong Answer[2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
89 ms |
780 KB |
Wrong Answer[5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
119 ms |
756 KB |
Wrong Answer[5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
692 KB |
Wrong Answer[5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
82 ms |
492 KB |
Wrong Answer[2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
