제출 #414552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
414552		Runtime_error_	도서관 (JOI18_library)	C++14	100 / 100	567 ms	320 KiB

library

#include <bits/stdc++.h>
#include "library.h"
#define mid (l+r)/2
#define pb push_back
#define mp make_pair
using namespace std;
int n;

int GetNext(int cur,vector<int> &PotentialNext){
    vector<int> Next;
    for(int i=0;i<n;i++)
        if(PotentialNext[i] == 1)
            Next.pb(i);

    if(Next.size() == 1)
        return Next[0];
    int l = 0,r = Next.size()-1;
    while(r!=l){
        vector<int> Left(n,0);
        for(int i=l;i<=mid;i++)
            Left[ Next[i] ] = 1;
        int without = Query(Left);
        Left[cur] = 1;
        int with = Query(Left);
        if(without == with )//then cur is adjacent with one element from the first half
            r = mid;                //because when adding cur the answer is still the same
        else
            l = mid+1;
    }
    return Next[l];
}

void Solve(int N){
    if(N == 1)
        return void(Answer({1}));
    n = N;
    vector<int> ask(n,1),ret;

    //N queries
    for(int i=0;i<n;i++){
        ask[i] = 0;
        if(Query(ask) == 1){
            ret.pb(i);
            break;
        }
        ask[i] = 1;
    }
    //the remaining number is deceasing by one every time so it is 2*sum(log2(i)) 1<=i<=n-1
    for(int i=1;i<n;i++){
        //now excluding the previous elements the i-the element is only adjacent with element i+1
        int cur = GetNext(ret.back(),ask);
        ask[cur] = 0;
        ret.pb(cur);
    }

    for(auto &o:ret)
        ++o;

    Answer(ret);

}

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