Submission #704959

#	Time	Username	Problem	Language	Result	Execution time	Memory
704959		piOOE	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	3049 ms	700 KiB

dango3

#include "dango3.h"

#include <bits/stdc++.h>

using namespace std;

void Solve(int n, int m) {
    const int N = n * m;

    vector<int> ord(N);
    iota(ord.begin(), ord.end(), 0);

    vector<vector<int>> in(m);

    vector<bool> used(N);
    vector<int> except(N);

    auto ask = [&](int i) {
        int top = 0;

        for (int j : in[i]) {
            used[j] = true;
        }

        for (int x : ord) {
            if (!used[x]) {
                except[top++] = x + 1;
            }
        }

        for (int j : in[i]) {
            used[j] = false;
        }

        return Query(vector(except.begin(), except.begin() + top));
    };

    for (int x : ord) {
        int lo = -1, hi = m - 1;

        while (lo + 1 < hi) {
            int mid = (lo + hi) / 2;

            in[mid].push_back(x);

            if (ask(mid) == m - 1) {
                hi = mid;
            } else {
                lo = mid;
            }

            in[mid].pop_back();
        }

        in[hi].push_back(x);
    }

    for (auto &y : in) {
        for (int &x : y) {
            x += 1;
        }

        Answer(y);
    }
}

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