oj.uz

Submission #958554

# Submission time Handle Problem Language Result Execution time Memory
958554 2024-04-06T03:18:13 Z gaga999 Super Dango Maker (JOI22_dango3) C++17
100 / 100
 1744 ms 1116 KB 
#include <bits/stdc++.h>
using namespace std;
void Solve(int N, int M);

int Query(const std::vector<int> &x);
void Answer(const std::vector<int> &a);

namespace
{
    int S;
    int q(vector<bool> b)
    {
        vector<int> x;
        for (int i = 0; i < S; i++)
        {
            if (b[i])
                x.push_back(i + 1);
        }
        return Query(x);
    }
    void a(vector<int> v)
    {
        for (auto &t : v)
        {
            t++;
        }
        Answer(v);
    }
} // namespace

void Solve(int N, int M)
{
    S = N * M;
    vector<vector<int>> dangobox(M);
    for (int i = 0; i < S; i++)
    {
        int l, r;
        l = -1;
        r = M - 1;
        while (l + 1 != r)
        {
            int m = (l + r) / 2;
            vector<bool> b(S, true);
            for (int j = 0; j <= m; j++)
            {
                for (int t : dangobox[j])
                {
                    b[t] = false;
                }
            }
            b[i] = false;
            if (q(b) == M - m - 2)
                l = m;
            else
                r = m;
        }
        dangobox[r].push_back(i);
    }
    for (int i = 0; i < M; i++)
    {
        a(dangobox[i]);
    }
}

Subtask #1
2.0 / 2.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 508 KB Output is correct
2 Correct 13 ms 344 KB Output is correct
3 Correct 13 ms 344 KB Output is correct
4 Correct 13 ms 600 KB Output is correct
5 Correct 11 ms 344 KB Output is correct
6 Correct 11 ms 352 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 596 KB Output is correct
2 Correct 373 ms 360 KB Output is correct
3 Correct 415 ms 856 KB Output is correct
4 Correct 456 ms 572 KB Output is correct
5 Correct 367 ms 828 KB Output is correct
6 Correct 352 ms 572 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 1549 ms 664 KB Output is correct
2 Correct 1516 ms 1116 KB Output is correct
3 Correct 1744 ms 720 KB Output is correct
4 Correct 1659 ms 716 KB Output is correct
5 Correct 1417 ms 920 KB Output is correct
6 Correct 1386 ms 680 KB Output is correct