Submission #1262908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262908		norman165	Super Dango Maker (JOI22_dango3)	C++20	0 / 100	197 ms	736 KiB

dango3

#include "dango3.h"
#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
// #define int long long
#define yes() cout << "YES\n"
#define no() cout << "NO\n"

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

// const int inf = 1e18;
// const int mod = 1e9 + 7;
// const int maxn = 1e6;
// const int mod1 = 998244353;
// const int mod2 = 1e18 + 1;
// const int mod3 = 1e9 + 9;
// const int mod4 = 333333333;
// const int mod5 = 200000;
// const int mod6 = 10007;
// const int k = 3000;
// const int w = 1e5;
// const ld EPS = 1e-8;

int LOG = 30;

int ask(vector<int> a) {
    return Query(a);
}

void Solve(int n, int m) {
    vector<vector<int>> ans;
    set<int> st;
    int x = m;
    vector<int> next(m);
    int prime = 0;

    for (int i = 0; i < n * m; i++) {
        vector<int> go;
        for (int j = 0; j <= i; j++) go.push_back(j + 1);
        if (ask(go) == prime + 1) {
            next[prime] = i;
            prime++;
        }
    }

    prime = -1;
    vector<int> use;
    for (int i = 0; i < n * m; i++) use.push_back(i);
    while (x--) {
        vector<int> res;
        prime++;

        int idx = next[prime];
        res.push_back(idx);
        st.insert(idx);

        int idx1 = -1;
        for (int j = 0; j < use.size(); j++) if (use[j] == idx) idx1 = j;
        int y = n - 1;
        while (y--) {
            int l = 0;
            int r = idx1;

            while (r - l > 1) {
                int mid = (l + r) / 2;
                vector<int> go;

                for (int j = 0; j < mid; j++) go.push_back(use[j] + 1);
                for (int& j : res) go.push_back(j + 1);

                if (ask(go) >= 1) r = mid;
                else l = mid;
            }

            res.push_back(use[l] + 1);
            idx1 = l;
            // int l = -1;
            // int r = idx;
            //
            // while (r - l > 1) {
            //     int mid = (l + r) / 2;
            //     vector<int> go;
            //
            //     for (int j = 0; j <= mid; j++) if (!st.count(j)) go.push_back(j + 1);
            //     for (int& j : res) go.push_back(j + 1);
            //
            //     if (ask(go) >= 1) r = mid;
            //     else l = mid;
            // }
            //
            // idx = l;
            // res.push_back(l + 1);
        }
        // for (int i = idx - 1; i >= -1; i--) {
        //     vector<int> go;
        //     for (int j = 0; j <= i; j++) if (!st.count(j)) go.push_back(j + 1);
        //     for (int& j : res) go.push_back(j + 1);
        //     if (ask(go) == 0) {
        //         res.push_back(i + 1);
        //     }
        // }

        use.clear();
        for (int j = 0; j < n * m; j++) if (!st.count(j)) use.push_back(j);
        for (int& i : res) st.insert(i);
        for (int& i : res) i++;
        ans.push_back(res);
    }

    for (auto& i : ans) Answer(i);
}

// signed main() {
//     // cout.precision(16);
//
//     ios::sync_with_stdio(false);
//     cin.tie(nullptr);
//
//     int t = 1;
//     // cin >> t;
//
//     // while (t--) {
//     //     solve();
//     // }
// }

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