Submission #1145365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145365		lightentheshadow	Library (JOI18_library)	C++20	100 / 100	120 ms	432 KiB

library

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

bool found[1005];
void Solve(int n) {
    vector<int> ans; ans.clear();

    if (n <= 2) {
        for (int i = 1; i <= n; i++)
            ans.push_back(i);
        Answer(ans);
        return ;
    }
    vector<int> ask;
    for (int i = 1; i <= n; i++)
        ask.push_back(0);

    /// Find one of the sides
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            if (j == i) ask[j - 1] = 0;
                else ask[j - 1] = 1;
        int res = Query(ask);
        if (res == 1) {
            ans.push_back(i);
            found[i] = 1;
            break;
        }
    }

    /// Find other ones
    vector<int> contender, A, B;
    for (int turn = 2; turn <= n; turn++) {
        contender.clear();
        for (int i = 1; i <= n; i++)
            if (!found[i]) contender.push_back(i);

        while (contender.size() > 1) {
            A.clear(); B.clear();

            /// Split two sides
            for (int i = 0; i < contender.size(); i++) {
                if (i % 2) A.push_back(contender[i]);
                    else B.push_back(contender[i]);
            }

            /// Ask set A
            for (int i = 0; i < n; i++)
                ask[i] = 0;

            for (auto x: A)
                ask[x - 1] = 1;

            int res = Query(ask);
            ask[ans.back() - 1] = 1;
            int res2 = Query(ask);
            if (res == res2) contender = A;
                else contender = B;
        }

        ans.push_back(contender[0]);
        found[contender[0]] = 1;
    }

    Answer(ans);
    return ;
}

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