Submission #1271262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271262		Double_Slash	Super Dango Maker (JOI22_dango3)	C++20	100 / 100	109 ms	664 KiB

dango3

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

using namespace std;
#define all(x) x.begin(), x.end()

void Solve(int N, int M) {
    bool dead[N * M + 1]{};
    for (int t = M; t--;) {
        vector<int> rem;
        for (int i = 1; i <= N * M; ++i) {
            if (not dead[i]) rem.emplace_back(i);
        }
        shuffle(all(rem), random_device());
        vector<int> a;
        for (int i = N, last = rem.size(); i--;) {
            auto q = [&] (int j) {
                if (j < N - (int) a.size()) return false;
                vector<int> b(rem.begin(), rem.begin() + j);
                b.insert(b.end(), all(a));
                return !!Query(b);
            };
            int j = last;
            for (int k = q(j - 4) ? 2 << __lg(j -= 4) : 4; k >>= 1;) j -= q(j - k) * k;
            a.emplace_back(rem[last = j - 1]);
        }
        for (int i: a) dead[i] = true;
        Answer(a);
    }
}

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 78 / 78