Submission #1128879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128879		vladilius	Super Dango Maker (JOI22_dango3)	C++20	22 / 100	202 ms	636 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--){
        while (i <= n * m && Query(a) < 1){
            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: 0 / 78