Submission #1273082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273082		Icelast	Super Dango Maker (JOI22_dango3)	C++20	100 / 100	476 ms	600 KiB

dango3

#include "dango3.h"

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rd

long long rd(long long l, long long h) {
    return l + rng() % (h - l + 1);
}

namespace {

int variable_example = 1;

}  // namespace

void Solve(int N, int M) {
    vector<int> p(N*M+1);
    iota(p.begin()+1, p.end(), 1);
    vector<bool> gone(N*M+1, false);
    for(int i = 1; i <= M; i++){
        shuffle(p.begin()+1, p.end(), rng);
        int l = 1, r = N*M, mid;
        while(l <= r){
            mid = (l+r)/2;
            vector<int> x;
            for(int ii = 1; ii <= mid; ii++){
                int i = p[ii];
                if(gone[i]) continue;
                x.push_back(i);
            }
            if(Query(x)){
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        vector<bool> ban(N*M+1, false);
        for(int ii = 1; ii <= l; ii++){
            int i = p[ii];
            if(gone[i]) continue;
            ban[i] = true;
            vector<int> x;
            for(int ii = 1; ii <= l; ii++){
                int i = p[ii];
                if(gone[i]) continue;
                if(ban[i]) continue;
                x.push_back(i);
            }
            if(Query(x) == 0){
                ban[i] = false;
            }
        }
        vector<int> x;
        for(int ii = 1; ii <= l; ii++){
            int i = p[ii];
            if(gone[i]) continue;
            if(ban[i]) continue;
            gone[i] = true;
            x.push_back(i);
        }
        Answer(x);
    }
}

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