Submission #1146874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146874		anmattroi	Library (JOI18_library)	C++17	100 / 100	122 ms	428 KiB

library

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

void Solve(int N) {
	vector<int> solved;
	vector<int> cl(N, 0);
    vector<int> M(N, 1);

    if (N == 1) {
        vector<int> xd(1, 1);
        Answer(xd);
        return;
    }
	for (int i = 0; i < N; i++) {
        M[i] = 0;
        int A = Query(M);
        if (A == 1) {
            solved.emplace_back(i);
            cl[i] = 1;
            break;
        }
        M[i] = 1;
	}
	for (int i = 0; i < N; i++) M[i] = 0;

    for (int step = 1; step < N-1; step++) {
        vector<int> indices;
        for (int i = 0; i < N; i++)
            if (!cl[i]) indices.emplace_back(i);

        int lo  = -1, hi = indices.size()-1;
        while (hi - lo > 1) {
            int mid = (lo + hi) >> 1;
            int A, B;
            for (int i : solved) M[i] = 1;
            for (int i = 0; i <= mid; i++) M[indices[i]] = 1;
            A = Query(M);
            for (int i : solved) M[i] = 0;
            B = Query(M);
            for (int i = 0; i < N; i++) M[i] = 0;
            if (A == B)
                hi = mid;
            else lo = mid;
        }
        cl[indices[hi]] = 1;
        solved.emplace_back(indices[hi]);
    }

    for (int i = 0; i < N; i++) if (!cl[i]) {solved.emplace_back(i); break;}
    for (int i = 0; i < N; i++) ++solved[i];
	Answer(solved);
}

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