Submission #704313

#	Time	Username	Problem	Language	Result	Execution time	Memory
704313		bachhoangxuan	Park (JOI17_park)	C++17	47 / 100	321 ms	576 KiB

park

#include<bits/stdc++.h>
#include "park.h"
using namespace std;
int n;
namespace sub1{
    int place[255];
    void solve(){
        for(int i=0;i<n;i++){
            place[i]=1;
            for(int j=i+1;j<n;j++){
                place[j]=1;
                if(Ask(i,j,place)) Answer(i,j);
                place[j]=0;
            }
            place[i]=0;
        }
        return;
    }
}
namespace sub2{
    int place[1405];
    bool in(int u,int a){
        if(a==0  || a==u) return true;
        for(int i=0;i<n;i++) place[i]=(i!=a);
        return !Ask(0,u,place);
    }
    void solve(){
        vector<int> x={0,n-1};
        for(int i=1;i<n-1;i++){
            int lt=1,rt=(int)x.size()-1,res=1;
            while(rt>=lt){
                int mid=(lt+rt)>>1;
                if(in(i,x[mid])) lt=mid+1;
                else{res=mid;rt=mid-1;}
            }
            x.insert(x.begin()+res,i);
        }
        for(int i=0;i<n-1;i++) Answer(min(x[i],x[i+1]),max(x[i],x[i+1]));
    }
}
namespace sub3{
    int place[1405];
    vector<int> child[1405];
    void dfs(int u){
        vector<int> nxt;
        for(int i=0;i<n;i++) place[i]=0;
        place[u]=1;
        for(int x:child[u]){
            place[x]=1;
            if(Ask(min(u,x),max(u,x),place)){
                Answer(min(u,x),max(u,x));
                nxt.push_back(x);
            }
            place[x]=0;
        }
        if(nxt.empty()) return;
        place[u]=0;
        for(int i=0;i<n;i++) place[i]=1;
        for(int x:child[u]){
            if(x==u) continue;
            bool check=false;
            for(int v:nxt) check|=(v==x);
            if(check) continue;
            int lt=0,rt=(int)nxt.size()-1,res=0;
            while(rt>=lt){
                int mid=(lt+rt)>>1;
                for(int i=0;i<=mid;i++) place[nxt[i]]=0;
                if(Ask(min(u,x),max(u,x),place)) lt=mid+1;
                else{res=mid;rt=mid-1;}
                for(int v:nxt) place[v]=1;
            }
            child[nxt[res]].push_back(x);
        }
        for(int v:nxt) dfs(v);
    }
    void solve(){
        for(int i=1;i<n;i++) child[0].push_back(i);
        dfs(0);
    }
}
void Detect(int T, int N) {
    n=N;
	if(T==1) sub1::solve();
	else if(T==2) sub2::solve();
	else sub3::solve();
}
//g++ -std=c++14 -O2 -o grader grader.cpp park.cpp
/*
3
7
6
0 2
0 3
3 6
3 1
2 4
2 5
*/

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 0 / 30
• Subtask 5: 0 / 23