oj.uz

Submission #886375

# Submission time Handle Problem Language Result Execution time Memory
886375 2023-12-12T01:47:58 Z dong_liu Super Dango Maker (JOI22_dango3) C++17
7 / 100
 247 ms 772 KB 
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 436 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 436 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 524 KB Output is correct
2 Correct 7 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 4 ms 516 KB Output is correct
5 Correct 7 ms 344 KB Output is correct
6 Correct 7 ms 348 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 632 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 78.0

# Verdict Execution time Memory Grader output
1 Incorrect 247 ms 772 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -