Submission #951670

#	Time	Username	Problem	Language	Result	Execution time	Memory
951670		Pring	Super Dango Maker (JOI22_dango3)	C++17	0 / 100	209 ms	616 KiB

dango3

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

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

namespace {
    const int MXN = 405;
    int n, m;
    vector<int> cnt[MXN];
    vector<int> v;
    int found = 1;
    vector<int> two;

    int BSH(int id) {
        // cout << "BSH " << id << endl;
        int l = 0, r = found;
        while (l + 1 < r) {
            int mid = (l + r) >> 1;
            FOR(i, mid, r) v.push_back(cnt[i].front());
            int x = Query(v);
            FOR(i, mid, r) v.pop_back();
            if (x == m - 2) r = mid;
            else l = mid;
        }
        // cout << l << endl;
        return l;
    }

    void PUT(int id) {
        int f = 0;
        v.pop_back();
        for (auto &i : two) v.push_back(i);
        if (found == n) {
            cnt[BSH(id)].push_back(id);
            two.push_back(id);
            return;
        }
        int x = Query(v);
        if (x == m - 1) {
            cnt[found].push_back(id);
            found++;
        } else {
            cnt[BSH(id)].push_back(id);
            two.push_back(id);
            f = 1;
        }
        FOR(i, 0, two.size() - f) v.pop_back();
    }

    void miku() {
        FOR(i, 1, n * m) v.push_back(i);
        cnt[0].push_back(n * m);
        for (int i = n * m - 1; i > 0; i--) PUT(i);
        // FOR(i, 0, n) {
            // for (auto &j : cnt[i]) cout << j << ' ';
            // cout << endl;
        // }
        FOR(i, 0, m) {
            vector<int> ans(n);
            FOR(j, 0, n) ans[j] = cnt[j][i];
            Answer(ans);
        }
    }
}

void Solve(int N, int M) {
    ::n = N;
    ::m = M;
    miku();
}

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