Submission #1080356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080356		vjudge1	Library (JOI18_library)	C++14	100 / 100	358 ms	596 KiB

library

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

void Solve(int N)
{
	vector<int> M(N);
	vector<int> res(N);
	vector<int> rem(N);
	if(N <= 2){
        for(int i=0;i<N;i++) res[i] = i+1;
        Answer(res);
        return;
	}
	for(int i=0;i<N;i++) M[i] = 1;
    for(int i=0;i<N;i++){
        M[i] = 0;
        int A = Query(M);
        if(A == 1){
            res[0] = i+1;
            break;
        }
        M[i] = 1;
    }
    for(int i=0;i<N;i++) rem[i] = i+1;
    rem.erase(lower_bound(rem.begin(), rem.end(), res[0]));
    for(int i=1;i<N;i++){
        int L = 0, R = rem.size()-1;
        while(L <= R){
            int mid = (L + R) / 2;
            // cout << "!!! " << mid << '\n';
            for(int j=0;j<N;j++) M[j] = 0;
            for(int j=0;j<i;j++) M[res[j] - 1] = 1;
            for(int j=0;j<=mid;j++) M[rem[j] - 1] = 1;
            int v1 = Query(M);
            for(int j=0;j<i;j++) M[res[j] - 1] = 0;
            int v0 = Query(M);
            if(v0 == v1) R = mid-1;
            else L = mid+1;
        }
        // pos is L
        res[i] = rem[L];
        rem.erase(lower_bound(rem.begin(), rem.end(), res[i]));
    }
    Answer(res);
}

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