oj.uz

Submission #704959

# Submission time Handle Problem Language Result Execution time Memory
704959 2023-03-03T07:19:29 Z piOOE Super Dango Maker (JOI22_dango3) C++17
100 / 100
 3049 ms 700 KB 
#include "dango3.h"

#include <bits/stdc++.h>

using namespace std;

void Solve(int n, int m) {
    const int N = n * m;

    vector<int> ord(N);
    iota(ord.begin(), ord.end(), 0);

    vector<vector<int>> in(m);

    vector<bool> used(N);
    vector<int> except(N);

    auto ask = [&](int i) {
        int top = 0;

        for (int j : in[i]) {
            used[j] = true;
        }

        for (int x : ord) {
            if (!used[x]) {
                except[top++] = x + 1;
            }
        }

        for (int j : in[i]) {
            used[j] = false;
        }

        return Query(vector(except.begin(), except.begin() + top));
    };

    for (int x : ord) {
        int lo = -1, hi = m - 1;

        while (lo + 1 < hi) {
            int mid = (lo + hi) / 2;

            in[mid].push_back(x);

            if (ask(mid) == m - 1) {
                hi = mid;
            } else {
                lo = mid;
            }

            in[mid].pop_back();
        }

        in[hi].push_back(x);
    }

    for (auto &y : in) {
        for (int &x : y) {
            x += 1;
        }

        Answer(y);
    }
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 364 KB Output is correct
2 Correct 24 ms 340 KB Output is correct
3 Correct 23 ms 364 KB Output is correct
4 Correct 24 ms 372 KB Output is correct
5 Correct 24 ms 376 KB Output is correct
6 Correct 22 ms 368 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 767 ms 552 KB Output is correct
2 Correct 759 ms 568 KB Output is correct
3 Correct 765 ms 340 KB Output is correct
4 Correct 763 ms 340 KB Output is correct
5 Correct 754 ms 436 KB Output is correct
6 Correct 742 ms 476 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 2923 ms 660 KB Output is correct
2 Correct 2814 ms 700 KB Output is correct
3 Correct 3022 ms 656 KB Output is correct
4 Correct 2884 ms 564 KB Output is correct
5 Correct 3049 ms 696 KB Output is correct
6 Correct 2962 ms 572 KB Output is correct