Submission #1213089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213089		Zero_OP	Super Dango Maker (JOI22_dango3)	C++20	100 / 100	1750 ms	712 KiB

dango3

#include "dango3.h"
#include <bits/stdc++.h>

using namespace std;

namespace {

int variable_example = 1;

}  // namespace

void Solve(int N, int M) {
    vector<vector<int>> sticks(M);
    vector<bool> used(N * M + 1);
    for(int i = 1; i <= N * M; ++i){
        //put dango i in the first j that sticks[j] does not have color C[i] 
        if(i == 1){
            sticks[0].push_back(i);
            continue;
        } 

        int l = 0, r = M-1, first_placeable = -1;
        while(l <= r){
            int mid = l + r >> 1;
            for(auto it : sticks[mid]) used[it] = true; 
            vector<int> subset;
            for(int j = 1; j <= N * M; ++j) if(!used[j] && j != i) subset.push_back(j);
            if(M - Query(subset) == 2) l = mid + 1;
            else first_placeable = mid, r = mid - 1;
            for(auto it : sticks[mid]) used[it] = false;
        }
        assert(first_placeable != -1);
        sticks[first_placeable].push_back(i);
    }

    for(int i = 0; i < M; ++i) Answer(sticks[i]);

    //f(S) = minium cnt[i] (++cnt[a[x]], x \in S)
    //g(S) = maximum cnt[i] (++cnt[a[x]], x \in S) = M - f({1, 2, ..., N * M} \ S)
}

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