Submission #654365

#	Time	Username	Problem	Language	Result	Execution time	Memory
654365		minhnhatnoe	Library (JOI18_library)	C++14	100 / 100	468 ms	328 KiB

library

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

int find_edge(int n){
    vector<int> a(n, 1);
    for (int i=0; i<n; i++){
        a[i] = 0;
        if (Query(a) == 1) return i;
        a[i] = 1;
    }
    throw runtime_error("Unreachable");
}
vector<int> binsearch(int n, vector<int> &a, vector<int> &chosen){
    vector<int> q(n);
    for (int i=a.size()/2-1; i>=0; i--) q[a[i]] = 1;
    int f = Query(q);
    for (int i: chosen) q[i] = 1;
    int s = Query(q);
    if (f == s){
        vector<int> nxt;
        for (int i=a.size()/2-1; i>=0; i--) nxt.push_back(a[i]);
        return nxt;
    }
    else{
        vector<int> nxt;
        for (int i=a.size()/2; i<a.size(); i++) nxt.push_back(a[i]);
        return nxt;
    }
}
vector<int> inverse(int n, vector<int> &chosen){
    vector<bool> a(n, 1);
    for (int i: chosen) a[i] = false;
    vector<int> nxt;
    for (int i=0; i<a.size(); i++) if (a[i]) nxt.push_back(i);
    return nxt;
}
void Solve(int N){
    int n = N;
    if (n == 1){
        Answer({1});
        return;
    }
    int left = find_edge(n);
    // cout << "LEFT: " << left+1 << " ";
    vector<int> chosen = {left};
    for (int i=1; i<n; i++){
        vector<int> cand = inverse(n, chosen);
        while (cand.size() != 1){
            cand = binsearch(n, cand, chosen);
        }
        // cout << "CHOSE: " << cand[0] + 1 << " ";
        chosen.push_back(cand[0]);
    }
    for (int i=0; i<chosen.size(); i++) chosen[i]++;
    Answer(chosen);
}

Compilation message (stderr)

library.cpp: In function 'std::vector<int> binsearch(int, std::vector<int>&, std::vector<int>&)':
library.cpp:27:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for (int i=a.size()/2; i<a.size(); i++) nxt.push_back(a[i]);
      |                                ~^~~~~~~~~
library.cpp: In function 'std::vector<int> inverse(int, std::vector<int>&)':
library.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i=0; i<a.size(); i++) if (a[i]) nxt.push_back(i);
      |                   ~^~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i=0; i<chosen.size(); i++) chosen[i]++;
      |                   ~^~~~~~~~~~~~~~

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