Submission #545058

#	Time	Username	Problem	Language	Result	Execution time	Memory
545058		baluteshih	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	3527 ms	520 KiB

dango3

#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 (stderr)

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 / 2
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 78 / 78