oj.uz

Submission #940849

# Submission time Handle Problem Language Result Execution time Memory
940849 2024-03-07T18:44:35 Z borisAngelov Super Dango Maker (JOI22_dango3) C++17
100 / 100
 582 ms 868 KB 
#include "dango3.h"
#include <bits/stdc++.h>

using namespace std;

const int maxn = 10005;
const int maxm = 30;

int n, m;

vector<int> ans[maxm];

void divideAndConquer(vector<int> indexes, int groups)
{
    if (indexes.size() == n)
    {
        Answer(indexes);
        return;
    }

    int l = 0;
    int r = indexes.size() - 1;

    while (l <= r)
    {
        int mid = (l + r) / 2;

        vector<int> toQuery;

        for (int i = 0; i <= mid; ++i)
        {
            toQuery.push_back(indexes[i]);
        }

        if (Query(toQuery) >= groups / 2)
        {
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }

    int splitPos = l;

    vector<int> toLeft;
    vector<int> toRight;

    for (int i = 0; i <= splitPos; ++i)
    {
        toLeft.push_back(indexes[i]);
    }

    for (int i = splitPos + 1; i < indexes.size(); ++i)
    {
        toRight.push_back(indexes[i]);
    }

    vector<int> compressedLeft;
    vector<bool> removed(indexes.size(), false);

    for (int i = 0; i < toLeft.size(); ++i)
    {
        vector<int> toQuery;

        for (int j = 0; j < toLeft.size(); ++j)
        {
            if (i != j && removed[j] == false)
            {
                toQuery.push_back(toLeft[j]);
            }
        }

        if (Query(toQuery) == groups / 2)
        {
            toRight.push_back(toLeft[i]);
            removed[i] = true;
        }
        else
        {
            compressedLeft.push_back(toLeft[i]);
        }
    }

    toLeft = compressedLeft;

    divideAndConquer(toLeft, groups / 2);
    divideAndConquer(toRight, groups - groups / 2);
}

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

    vector<int> all;

    for (int i = 1; i <= n * m; ++i)
    {
        all.push_back(i);
    }

    divideAndConquer(all, m);
}

Compilation message

dango3.cpp: In function 'void divideAndConquer(std::vector<int>, int)':
dango3.cpp:15:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   15 |     if (indexes.size() == n)
      |         ~~~~~~~~~~~~~~~^~~~
dango3.cpp:55:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i = splitPos + 1; i < indexes.size(); ++i)
      |                                ~~^~~~~~~~~~~~~~~~
dango3.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (int i = 0; i < toLeft.size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~
dango3.cpp:67:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for (int j = 0; j < toLeft.size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 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 5 ms 348 KB Output is correct
2 Correct 5 ms 516 KB Output is correct
3 Correct 6 ms 348 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 604 KB Output is correct
2 Correct 96 ms 636 KB Output is correct
3 Correct 142 ms 604 KB Output is correct
4 Correct 148 ms 600 KB Output is correct
5 Correct 50 ms 656 KB Output is correct
6 Correct 48 ms 760 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 600 KB Output is correct
2 Correct 400 ms 844 KB Output is correct
3 Correct 582 ms 868 KB Output is correct
4 Correct 544 ms 796 KB Output is correct
5 Correct 176 ms 600 KB Output is correct
6 Correct 183 ms 732 KB Output is correct