Submission #940849

#	Time	Username	Problem	Language	Result	Execution time	Memory
940849		borisAngelov	Super Dango Maker (JOI22_dango3)	C++17	100 / 100	582 ms	868 KiB

dango3

#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 (stderr)

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 / 2
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 78 / 78