Submission #1162365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162365		zyq181	Library (JOI18_library)	C++20	100 / 100	118 ms	440 KiB

library

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

int n;
deque<int> rightside;
int start;

vector<int> q;
vector<int> qc;
bool determined[1010];

void findright(int numleft){
    vector<int> remain;
    for(int a=0; a<n; a++){
        if(!determined[a]) remain.push_back(a+1);
    }
    int lo = 0;
    int hi = numleft-1;
    while(lo < hi){
        int m = (lo + hi)/2;
        //lo to m
        fill(q.begin(), q.end(), 0);
        fill(qc.begin(), qc.end(), 1);
        for(int a=lo; a<=m; a++){
            q[remain[a]-1] = 1;
            qc[remain[a]-1] = 0;
        }
        for(auto it: rightside) qc[it-1] = 0;
        int r1 = Query(q);
        int r2 = Query(qc);
        if(r2 > r1) lo = m + 1;
        else hi = m;
    }
    int side = remain[lo];
    if(numleft == n){
        start = side;
        //cout << "START: " << start << '\n';
        determined[side-1] = true;
        return;
    }
    //cout << "RIGHT: " << side << '\n';
    rightside.push_front(side);
    determined[side-1] = true;
}

void Solve(int N){
    n = N;
    q.resize(n, 0);
    qc.resize(n, 0);
    for(int a=n; a>=1; a--){
        findright(a);
    }
    vector<int> ans;
    ans.resize(n);
    ans[0] = start;
    for(int a=1; a<n; a++) ans[a] = rightside[a-1];
    Answer(ans);
    return;
}

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