oj.uz

Submission #704313

# Submission time Handle Problem Language Result Execution time Memory
704313 2023-03-02T03:28:39 Z bachhoangxuan Park (JOI17_park) C++17
47 / 100
 321 ms 576 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 6 ms 340 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 7 ms 340 KB Output is correct
5 Correct 9 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 476 KB Output is correct
2 Correct 80 ms 488 KB Output is correct
3 Correct 89 ms 488 KB Output is correct
4 Correct 151 ms 468 KB Output is correct
5 Correct 154 ms 488 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 436 KB Output is correct
2 Correct 218 ms 460 KB Output is correct
3 Correct 169 ms 448 KB Output is correct
4 Correct 162 ms 468 KB Output is correct
5 Correct 161 ms 460 KB Output is correct
6 Correct 177 ms 452 KB Output is correct
7 Correct 166 ms 484 KB Output is correct
8 Correct 206 ms 576 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 468 KB Output is correct
2 Incorrect 321 ms 460 KB Wrong Answer[5]
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 468 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -