제출 #1231594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231594		MarwenElarbi	Park (JOI17_park)	C++20	67 / 100	310 ms	732 KiB

park

#include "park.h"
#include <bits/stdc++.h>
using namespace std;

int n;
int place_a[1405];
int place_b[1405];
vector<int> tab;
vector<int> cur;
int parent[1405];
int depth[1405];
vector<int> a;
vector<int> b;
int binary_search_a(int start){
    int l=-1;
    int r=a.size()-1;
    while(r-l>1){
        int mid=(r+l)/2;
        for (int i = 0; i <= mid; ++i)
        {
            place_a[a[i]]=0;
        }
        if(Ask(0,start,place_a)) l=mid;
        else r=mid;
        for (int i = 0; i <= mid; ++i)
        {
            place_a[a[i]]=1;
        }   
    }
    return r;
}
int binary_search_b(int start){
    int l=-1;
    int r=b.size();
    while(r-l>1){
        int mid=(r+l)/2;
        for (int i = 0; i <= mid; ++i)
        {
            place_b[b[i]]=0;
        }
        if(Ask(0,start,place_b)) l=mid;
        else r=mid;
        for (int i = 0; i <= mid; ++i)
        {
            place_b[b[i]]=1;
        }
    }
    return r;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int ans[1405];
int place[1405];
void daq(int start,int l,int r,vector<int> v){
    if(l>r) return;
    if(l==r){
        ans[l]=v.back();
        return;
    }else if(r==1&&l==0){
        ans[0]=start;
        ans[1]=(v.back()==start ? v[0] : v[1]);
        return;
    }
    int mid=uniform_int_distribution<int>(0,(int)v.size()-1)(rng);
    while(v[mid]==0) mid=uniform_int_distribution<int>(0,(int)v.size()-1)(rng);
    int y=v[mid];
    vector<int> v1;
    vector<int> v2;
    for (int i = 0; i < v.size(); ++i)
    {
        if(v[i]==0||v[i]==y){
            v1.push_back(v[i]);
            continue;
        }
        place[v[i]]=0;
        if(Ask(0,y,place)) v2.push_back(v[i]);
        else v1.push_back(v[i]);
        place[v[i]]=1; 
    }
    daq(start,l,l+v1.size()-1,v1);
    daq(start,l+v1.size(),r,v2);
}
void Detect(int T, int N){
    n=N;
    for (int i = 0; i < n; ++i) place_b[i]=place_a[i]=place[i]=1;
    memset(depth,-1,sizeof depth);
    memset(parent,-1,sizeof parent);
    depth[0]=0;
    a.push_back(0);
    for (int i = 1; i < n; ++i)
    {
        b.push_back(i);
    }
    while(a.size()<n){
        int x=b.back();
        vector<int> cur;
        cur.push_back(x);
        b.pop_back();
        int y=a[binary_search_a(x)];
        int z=binary_search_b(x);
        while(z<b.size()){
            cur.push_back(b[z]);
            vector<int> nab;
            for (int i = 0; i < b.size(); ++i) if(i!=z) nab.push_back(b[i]);
            b=nab;
            z=binary_search_b(x);
        }
        cur.push_back(y);
        /*cout <<y<<endl;
        cout << "cur :";
        for (auto u:cur) cout <<u<<" ";
            cout <<endl;*/
        daq(y,0,cur.size()-1,cur);
        for (int i = 1; i < cur.size(); ++i)
        {
            a.push_back(ans[i]);
            parent[ans[i]]=ans[i-1];
            depth[ans[i]]=depth[ans[i-1]]+1;
        }
        /*cout << "b :";
        for(auto u:b) cout <<u<<" ";
            cout <<endl;*/
        vector<pair<int,int>> inter;
        for (int i = 0; i < a.size(); ++i) inter.push_back({depth[a[i]],a[i]});
        sort(inter.begin(),inter.end(),greater<pair<int,int>>());
        for (int i = 0; i < a.size(); ++i)
        {
            a[i]=inter[i].second;
        }
        /*cout << "a :";
        for(auto u:a) cout <<u<<" ";
            cout <<endl;*/
    }
    for (int i = 1; i < n; ++i)
    {
        int x=parent[i];
        int y=i;
        if(x>y) swap(x,y);
        Answer(x,y);
    }
    return;
}

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