Submission #1128887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128887		vladilius	Super Dango Maker (JOI22_dango3)	C++20	100 / 100	185 ms	688 KiB

dango3

#include <bits/stdc++.h>
#include "dango3.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

void Solve(int n, int m){
    vector<int> A;
    for (int i = 0; i <= n * m; i++) A.pb(i);
    
    mt19937 rng((int) time(0));
    shuffle(A.begin() + 1, A.end(), rng);

    vector<int> a, p, b;
    int tt = m, i = 1;
    while (tt--){
        auto check1 = [&](int k){
            vector<int> a1 = a;
            for (int j = i; j <= k; j++){
                a1.pb(A[j]);
            }
            return Query(a1) < 1;
        };
        
        int l1 = i - 1, r1 = n * m;
        while (l1 + 1 < r1){
            int k = (l1 + r1) / 2;
            if (check1(k)){
                l1 = k;
            }
            else {
                r1 = k - 1;
            }
        }
        
        while (check1(l1)) l1++;
        while (i <= l1) a.pb(A[i++]);

        p.clear();
        b = a;
        int TT = n, st = 0;
        while (TT--){
            bool ind = 0;
            for (int d = 0; d < 5; d++){
                vector<int> a1 = a;
                a1.erase(find(a1.begin(), a1.end(), b[st]));
                if (Query(a1) < 1){
                    ind = 1;
                    st++;
                    break;
                }
                a = a1;
                p.pb(b[st++]);
            }
            if (ind) continue;
            
            auto check = [&](int k){
                vector<int> a1 = a;
                for (int f = st; f <= k; f++){
                    a1.erase(find(a1.begin(), a1.end(), b[f]));
                }
                return Query(a1) < 1;
            };
            
            int l = st - 1, r = (int) b.size() - n;
            while (l + 1 < r){
                int k = (l + r) / 2;
                if (check(k)){
                    r = k - 1;
                }
                else {
                    l = k;
                }
            }
            while (!check(l)) l++;
            
            for (int f = st; f < l; f++){
                a.erase(find(a.begin(), a.end(), b[f]));
                p.pb(b[f]);
            }
            st = l + 1;
        }
        Answer(a);
        a = p;
    }
}

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