Submission #544815

#	Time	Username	Problem	Language	Result	Execution time	Memory
544815		Ronin13	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	4077 ms	800 KiB

dango3

#include "dango3.h"
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define ull unsigned ll
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;


void Solve(int N, int M) {
    int n = N;
    int m = M;
    vector <vector<int> > dango(m + 1);
    vector <bool> used(n * m + 1, false);
    for(int i = 1; i <= n * m; i++){
        int l = 0, r = m;
        used[i] = true;
        while(l + 1 < r){
            int mid = (l + r) / 2;
            for(int to : dango[mid]) used[to] = true;
            vector <int> vec;
            for(int j = 1; j <= n * m; j++){
                if(!used[j]) vec.pb(j);
            }
            for(int to : dango[mid]) used[to] = false;
            int x = Query(vec);
            if(x <= m - 2)l = mid;
            else r = mid;
        }
        used[i] = false;
        dango[r].pb(i);
    }
    for(int i = 1; i <= m; i++){
        Answer(dango[i]);
    }
}

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