Submission #941647

#	Time	Username	Problem	Language	Result	Execution time	Memory
941647		Pannda	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	191 ms	860 KiB

dango3

#include "dango3.h"

#include <bits/stdc++.h>
using namespace std;

void Solve(int n, int m) {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    auto query = [&](vector<int> x) -> int {
        for (int &i : x) i++;
        return Query(x);
    };
    auto answer = [&](vector<int> x) -> void {
        for (int &i : x) i++;
        Answer(x);
    };

    vector<int> rem(n * m);
    iota(rem.begin(), rem.end(), 0);

    for (int t = 0; t < m; t++) {
        shuffle(rem.begin(), rem.end(), rng);
        int l = n, r = rem.size();
        while (l < r) {
            int m = (l + r) >> 1;
            if (query(vector<int>(rem.begin(), rem.begin() + m)) > 0) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        int C = l;
        vector<int> f(rem.begin(), rem.begin() + C);
        int cur = query(f);
        vector<int> new_rem(rem.begin() + C, rem.end());
        while (f.size() > n) {
            int i = f.back();
            f.pop_back();
            int nxt = query(f);
            if (nxt == 0) {
                f.insert(f.begin(), i);
            } else {
                new_rem.push_back(i);
            }
        }
        rem = new_rem;
        answer(f);
    }
}

Compilation message (stderr)

dango3.cpp: In function 'void Solve(int, int)':
dango3.cpp:35:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |         while (f.size() > n) {
      |                ~~~~~~~~~^~~
dango3.cpp:33:13: warning: unused variable 'cur' [-Wunused-variable]
   33 |         int cur = query(f);
      |             ^~~

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