Submission #886375

#	Time	Username	Problem	Language	Result	Execution time	Memory
886375		dong_liu	Super Dango Maker (JOI22_dango3)	C++17	7 / 100	247 ms	772 KiB

dango3

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

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;
using pii = pair<int, int>;

/*
int s(int n) {
    return n/4000;
}

int calc(int l, int r) {
    if (s(r) == s(l-1)) return 1;
    if (l == r) return 1;
    int m = (l+r)/2;
    return 1+calc(l,m)+calc(m+1,r);
}
*/

#ifdef LOCAL

int n, m, a[int(1e4)+1];

int Query(vector<int> v) {
    vector<int> c(n);
    for (int i : v) c[a[i]-1]++;
    // for (int i : v) cout << i << ' ';
    // cout << "| GOT " << *min_element(begin(c),end(c)) << endl;
    return *min_element(begin(c),end(c));
}

void Answer(vector<int> v) {
    for (int x : v) cout << x << ' ';
    cout << '\n';
}

#else

#include "dango3.h"

#endif

void Solve(int n, int m) {
    vector<int> on(n*m+1);
    for (int i = 1; i <= n*m - (m-1); i++)
        on[i] = 1;
    auto get_v = [&]() {
        vector<int> v;
        for (int i = 1; i <= n*m; i++) if (on[i]) v.push_back(i);
        return v;
    };
    int c = n*m - (m-1);
    for (int i = 1; i <= n*m; i++)
        if (on[i]) {
            on[i] = 0;
            if (Query(get_v())) {
                c--;
                if (c == n) break;
            } else {
                on[i] = 1;
            }
        }
    auto base = get_v();
    vector<int> a(n*m+1);
    int id = 0;
    for (int i : base) a[i] = ++id;
    for (int i : base) {
        vector<int> p;
        for (int j = 1; j <= n*m; j++) if (!a[j]) p.push_back(j);
        queue<pii> q;
        q.push({0, sz(p)-1});
        while (sz(q)) {
            auto [l,r] = q.front(); q.pop();
            auto v = base;
            v.erase(find(begin(v), end(v), i));
            for (int j = l; j <= r; j++) v.push_back(p[j]);
            if (Query(v)) {
                if (l == r) a[p[l]] = a[i];
                else {
                    int m = (l+r)/2;
                    q.push({l,m}), q.push({m+1,r});
                }
            }
        }
    }
    vector<vector<int>> at(n+1);
    for (int i = 1; i <= n*m; i++) {
        assert(a[i]);
        at[a[i]].push_back(i);
        // cout << a[i] << ' ';
    }
    // cout << '\n';
    // return;
    for (int it = 0; it < m; it++) {
        vector<int> v;
        for (int i = 1; i <= n; i++) {
            assert(sz(at[i]));
            v.push_back(at[i].back());
            at[i].pop_back();
        }
        Answer(v);
    }
}

#ifdef LOCAL

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n*m; i++) cin >> a[i];
    Solve(n, m);
}

#endif

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