Submission #133697

#	Time	Username	Problem	Language	Result	Execution time	Memory
133697		doowey	Library (JOI18_library)	C++14	100 / 100	551 ms	416 KiB

library

#include <bits/stdc++.h>
#include "library.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

int query(vector<int> t){
    bool yes = false;
    for(auto p : t) yes |= (p > 0);
    if(!yes) return 0;
    return Query(t);
}

int use[1005];

void Solve(int n){
    if(n==1){
        Answer({1});
        return;
    }
    if(n == 2){
        Answer({1,2});
        return;
    }
    for(int j = 0 ; j < n; j ++ ) use[j] = 0;
	vector<int> p(n);
    vector<int> answ;
    for(int i = 0 ; i < n; i ++ )
        p[i] = 1;
    int las;
    for(int i = 0 ; i < n; i ++ ){
        p[i]=0;
        if(query(p) == 1){
            answ.push_back(i);
            use[i] = 1;
            break;
        }
        p[i]=1;
    }
    int lf, rf, md;
    int cur, nx;
    vector<int> ni;
    for(int i = 1 ; i < n; i ++ ){
        las = answ.back();
        ni.clear();
        for(int j = 0 ; j < n; j ++ ){
            if(use[j] == 0){
                ni.push_back(j);
            }
        }
        lf = 0;
        rf = (int)ni.size() - 1;
        while(lf < rf){
            md = (lf + rf) / 2;
            for(int t = 0 ;t < n; t ++ )
                p[t] = 0;
            for(int t = 0 ; t <= md; t ++ )
                p[ni[t]] = 1;
            for(auto v : answ)
                p[v] = 0;
            cur = query(p);
            p[las] = 1;
            nx = query(p);
            if(cur == nx){
                rf = md;
            }
            else{
                lf = md + 1;
            }
        }
        answ.push_back(ni[rf]);
        use[ni[rf]] = 1;
    }
    for(int i = 0 ; i < n ; i ++ )
        answ[i] ++ ;
    Answer(answ);
}

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