oj.uz

Submission #864406

# Submission time Handle Problem Language Result Execution time Memory
864406 2023-10-22T19:17:09 Z Dec0Dedd Super Dango Maker (JOI22_dango3) C++17
100 / 100
 2234 ms 1144 KB 
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 348 KB Output is correct
2 Correct 15 ms 348 KB Output is correct
3 Correct 18 ms 352 KB Output is correct
4 Correct 16 ms 512 KB Output is correct
5 Correct 16 ms 356 KB Output is correct
6 Correct 15 ms 356 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 624 KB Output is correct
2 Correct 493 ms 636 KB Output is correct
3 Correct 555 ms 1144 KB Output is correct
4 Correct 556 ms 856 KB Output is correct
5 Correct 495 ms 780 KB Output is correct
6 Correct 502 ms 872 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 1959 ms 856 KB Output is correct
2 Correct 1966 ms 856 KB Output is correct
3 Correct 2207 ms 996 KB Output is correct
4 Correct 2234 ms 816 KB Output is correct
5 Correct 1978 ms 984 KB Output is correct
6 Correct 1948 ms 1040 KB Output is correct