Submission #864406

#	Time	Username	Problem	Language	Result	Execution time	Memory
864406		Dec0Dedd	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	2234 ms	1144 KiB

dango3

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

using namespace std;

int n, m;

int mx(vector<int> v) {
    int cnt[n*m+1]={};
    for (auto u : v) ++cnt[u];

    vector<int> x;
    for (int i=1; i<=n*m; ++i) {
        if (cnt[i] == 0) x.push_back(i);
    }

    return m-Query(x);
}

void Solve(int _n, int _m) {
    n=_n, m=_m;
    vector<int> v[m+1];

    for (int i=1; i<=n*m; ++i) {
        int l=1, r=m-1, res=0;
        while (l <= r) {
            int md=(l+r)/2;
            v[md].push_back(i);
            if (mx(v[md]) > 1) l=md+1, res=md;
            else r=md-1;
            v[md].pop_back();
        } v[res+1].push_back(i);
    }

    for (int i=1; i<=m; ++i) {
        assert((int)v[i].size() == n);
        Answer(v[i]);
    }
}

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