Submission #1165662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165662		abcdxyz123	도서관 (JOI18_library)	C++20	100 / 100	150 ms	508 KiB

library

#include"library.h"
#include <bits/stdc++.h>
using namespace std;
int n;
int a[2005];
int nho[2005];
int ask(vector<int>vec,int lim,int x)
{
    if(vec.empty())return -1;
    vector<int>mask;
    for(int i=1;i<=n;i++)
    {
        mask.push_back(0);
    }
    for(int i=0;i<=lim;i++)
    {
        mask[vec[i]-1]=1;
    }
    mask[x-1]=0;
    int tmp=Query(mask);
    mask[x-1]=1;
    int delta =Query(mask)-tmp;
    if(delta==-1)return 2;
    else if(delta==0)return 1;
    else if(delta==1)return 0;
}
int FindAdj(int x,vector<int>vec)
{
    if(vec.empty())return -1;
    int lo=-1;
    int hi=vec.size()-1;
    if(ask(vec,hi,x)==0)return -1;
    while(hi-lo>1)
    {
        int mid=(lo+hi)/2;
        if(ask(vec,mid,x)>=1)
        {
            hi=mid;
        }
        else
        {
            lo=mid;
        }
    }
    return vec[hi];
}
void Solve(int N)
{
    n=N;
    if(N==1)
    {
        vector<int>tmp;
        tmp.push_back(1);
        Answer(tmp);
        return ;
    }
    else if(N==2)
    {
        vector<int>tmp;
        tmp.push_back(1);
        tmp.push_back(2);
        Answer(tmp);
        return ;
    }
    int l=n;
    int r=n;
    a[l]=1;
    nho[1]=1;
    vector<int>Cand;
    for(int i=1;i<=n;i++)
    {
        if(nho[i])continue;
        Cand.push_back(i);
    }
    int tmp=FindAdj(a[l],Cand);
    //cout<<a[l]<<' '<<tmp<<'\n';
    a[++r]=tmp;
    nho[tmp]=1;

    while(true)
    {
        vector<int>Cand;
        for(int i=1;i<=n;i++)
        {
            if(nho[i])continue;
            Cand.push_back(i);
        }
        int val=FindAdj(a[l],Cand);
        if(val==-1)break;
        nho[val]=1;
        a[--l]=val;
    }

    while(true)
    {
        vector<int>Cand;
        for(int i=1;i<=n;i++)
        {
            if(nho[i])continue;
            Cand.push_back(i);
        }
        int val=FindAdj(a[r],Cand);
        if(val==-1)break;
        nho[val]=1;
        a[++r]=val;
    }

    vector<int>ans;
    for(int i=l;i<=r;i++)
    {
        //cout<<a[i]<<' ';
        ans.push_back(a[i]);
    }
    //cout<<'\n';
    Answer(ans);

}

Compilation message (stderr)

library.cpp: In function 'int ask(std::vector<int>, int, int)':
library.cpp:26:1: warning: control reaches end of non-void function [-Wreturn-type]
   26 | }
      | ^

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81