oj.uz

Submission #545058

# Submission time Handle Problem Language Result Execution time Memory
545058 2022-04-03T13:20:46 Z baluteshih Super Dango Maker (JOI22_dango3) C++17
100 / 100
 3527 ms 520 KB 
#include "dango3.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()
#define pb push_back

namespace {

vector<int> comb(vector<int> &a, vector<int> &b) {
    vector<int> rt(SZ(a) + SZ(b));
    for (int i = 0; i < SZ(a); ++i)
        rt[i] = a[i];
    for (int i = 0; i < SZ(b); ++i)
        rt[i + SZ(a)] = b[i];
    return rt;
}

vector<int> sub(vector<int> &a, int l, int r) {
    vector<int> rt(r - l + 1);
    for (int i = l; i <= r; ++i)
        rt[i - l] = a[l];
    return rt;
}

int query(vector<int> q) {
    /*cerr << "Query ";
    for (int i : q)
        cerr << i << " ";
    cerr << "\n";*/
    int rt = Query(q);
    //cerr << "= " << rt << "\n";
    return rt;
}

}  // namespace

void Solve(int N, int M) {
    vector<int> bln(N * M + 1), gap(M + 1);
    vector<vector<int>> ans(M + 1);
    /*int nw = 0;
    for (int i = 1; i <= N * M; ++i) {
        vector<int> tmp(i);
        iota(ALL(tmp), 1);
        if (query(tmp) > nw) {
            bln[i] = ++nw;
            gap[nw] = i;
        }
    }*/
    for (int i = N * M; i >= 1; --i) {
        int l = 1, r = M;
        while (l < r) {
            int mid = (l + r) >> 1;
            vector<int> tmp;
            for (int k = 1; k <= N * M; ++k)
                if (bln[k] <= mid && k != i)
                    tmp.pb(k);
            if (query(tmp) < mid)
                r = mid;
            else
                l = mid + 1;
        }
        bln[i] = l;
    }

    for (int i = 1; i <= N * M; ++i)
        ans[bln[i]].pb(i);
    for (int i = 1; i <= M; ++i)
        Answer(ans[i]); 
}

Compilation message

dango3.cpp:24:13: warning: 'std::vector<int> {anonymous}::sub(std::vector<int>&, int, int)' defined but not used [-Wunused-function]
   24 | vector<int> sub(vector<int> &a, int l, int r) {
      |             ^~~
dango3.cpp:15:13: warning: 'std::vector<int> {anonymous}::comb(std::vector<int>&, std::vector<int>&)' defined but not used [-Wunused-function]
   15 | vector<int> comb(vector<int> &a, vector<int> &b) {
      |             ^~~~

Subtask #1
2.0 / 2.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 368 KB Output is correct
2 Correct 25 ms 384 KB Output is correct
3 Correct 27 ms 368 KB Output is correct
4 Correct 28 ms 340 KB Output is correct
5 Correct 20 ms 340 KB Output is correct
6 Correct 24 ms 360 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 674 ms 340 KB Output is correct
2 Correct 726 ms 432 KB Output is correct
3 Correct 850 ms 428 KB Output is correct
4 Correct 815 ms 428 KB Output is correct
5 Correct 684 ms 428 KB Output is correct
6 Correct 716 ms 424 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 2979 ms 516 KB Output is correct
2 Correct 3118 ms 520 KB Output is correct
3 Correct 3527 ms 512 KB Output is correct
4 Correct 3445 ms 520 KB Output is correct
5 Correct 2877 ms 516 KB Output is correct
6 Correct 2752 ms 516 KB Output is correct