Submission #1186852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186852		SalihSahin	Super Dango Maker (JOI22_dango3)	C++20	100 / 100	219 ms	724 KiB

dango3

#include "bits/stdc++.h"
#define pb push_back
#include "dango3.h"
using namespace std;

void Solve(int N, int M){
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    vector<int> rem;
    for(int i = 1; i <= N*M; i++){
        rem.pb(i);
    }
    for(int turn = 1; turn <= M; turn++){
        shuffle(rem.begin(), rem.end(), rng);

        int l = 0, r = rem.size()-1;
        while(l < r){
            int m = (l + r)/2;
            vector<int> check;
            for(int i = 0; i <= m; i++){
                check.pb(rem[i]);
            }
            int x = Query(check);
            if(x == 0) l = m + 1;
            else r = m;
        }

        vector<int> add, nrem;
        vector<int> cik(rem.size());

        for(int i = 0; i <= l; i++){
            vector<int> check;
            cik[i] = 1;
            for(int j = 0; j <= l; j++){
                if(!cik[j]) check.pb(rem[j]);
            }

            int x = Query(check);
            if(x >= 1) nrem.pb(rem[i]);
            else{
                add.pb(rem[i]);
                cik[i] = 0;
            }
        }

        for(int i = l+1; i < rem.size(); i++){
            nrem.pb(rem[i]);
        }

        rem = nrem;
        Answer(add);
    }
}

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