Submission #951656

#	Time	Username	Problem	Language	Result	Execution time	Memory
951656		Pring	Super Dango Maker (JOI22_dango3)	C++17	7 / 100	699 ms	776 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) {
            // cout << "L: " << l << ", R: " << r << endl;
            int mid = (l + r) >> 1;
            FOR(i, mid, r) v.push_back(cnt[i].front());
            // for (auto &i : v) cout << i << ' ';
            // cout << endl;
            int x = Query(v);
            // cout << "x: " << x << endl;
            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;
        // cout << "PUT " << id << endl;
        // cout << "TWO: ";
        // for (auto &i : two) cout << i << ' ';
        // cout << endl;
        v.pop_back();
        for (auto &i : two) v.push_back(i);
        if (found == n) {
            BSH(id);
        }
        // for (auto &i : v) cout << i << ' ';
        // cout << endl;
        int x = Query(v);
        if (x == m - 1) {
            // cout << "FOUND" << endl;
            cnt[found].push_back(id);
            found++;
        } else {
            cnt[BSH(id)].push_back(id);
            two.push_back(id);
            f = 1;
        }
        // for (auto &i : two) v.pop_back();
        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) {
        //     cout << cnt[i].size() << '\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: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 0 / 15
• Subtask 4: 0 / 78