Submission #1244274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244274		minhpk	Library (JOI18_library)	C++20	100 / 100	126 ms	516 KiB

library

#include <bits/stdc++.h>
#include "library.h"
using namespace std;
int n;
vector <int> res;
int del[1000005];
int ask(vector<int> q){
    vector <int> q1(n);
    for (auto p:q){
         q1[p-1]=1;
    }
    return Query(q1);
}

void Solve(int N){
    if (N==1){
        vector <int> pre;
        pre.push_back(1);
        Answer(pre);
        return;
    }
    n=N;
    int a=N;
    int sta;
    for (int i=1;i<=a;i++){
        vector <int> pre;
        for (int j=1;j<=a;j++){
             if (j==i){
                continue;
             }
             pre.push_back(j);
        }
        int val=ask(pre);
        if (val==1){
            sta=i;
            break;
        }
    }
    int last=sta;
    del[sta]=1;
    res.push_back(sta);
    for (int i=2;i<=a;i++){
         vector <int> pre;
         for (int j=1;j<=a;j++){
             if (del[j]){
                continue;
             }
             pre.push_back(j);
         }

         int l=0;
         int r=pre.size()-1;
         int pos=0;
         while (l<=r){
             int mid=(l+r)/2;
             vector <int> pre1(pre.begin(),pre.begin()+mid+1);
             int val=ask(pre1);
             pre1.push_back(last);
             int val1=ask(pre1);
             if (val==val1){
                 pos=mid;
                 r=mid-1;
             }else{
                 l=mid+1;
             }
         }
         int x=pre[pos];
         res.push_back(x);
         del[x]=1;
         last=x;
    }
    Answer(res);
}

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