Submission #883411

#	Time	Username	Problem	Language	Result	Execution time	Memory
883411		boris_mihov	Red-blue table (IZhO19_stones)	C++17	100 / 100	25 ms	2396 KiB

stones

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <vector>
#include <bitset>
#include <queue>
#include <set>

typedef long long llong;
const int MAXN = 1000 + 10;
const int MAXLOG = 20;

const llong INF = 4e18;
const int INTINF = 2e9;

int n, m;
char t[MAXN][MAXN];
int countMAX[MAXN];
std::vector <int> canAdd;
bool reversed;
int answer;

void solve()
{   
    if (n > m)
    {
        std::swap(n, m);
        reversed = true;
    } else
    {
        reversed = false;
    }

    int countLeft = n * m - m * ((n + 2) / 2);
    int rows = countLeft / ((m + 2) / 2);
    answer = m + rows;

    for (int i = 1 ; i <= n ; ++i)
    {
        t[i][m + 1] = '\0';
        for (int j = 1 ; j <= m ; ++j)
        {
            t[i][j] = '+';
        }
    }

    canAdd.clear();
    for (int i = 1 ; i <= rows ; ++i)
    {
        countMAX[i] = m - (m + 2) / 2;
        canAdd.push_back(i);
    }

    for (int i = rows + 1 ; i <= n ; ++i)
    {
        for (int col = 1 ; col <= m ; ++col)
        {
            t[i][col] = '-';
        }
    }

    for (int col = 1 ; col <= m ; ++col)
    {
        int needed = (n + 2) / 2 - (n - rows);
        assert(canAdd.size() >= needed);
        std::sort(canAdd.begin(), canAdd.end(), [&](int x, int y)
        {
            return countMAX[x] > countMAX[y];
        });

        for (int i = 0 ; i < needed ; ++i)
        {
            assert(countMAX[canAdd[i]] >= 0);
            t[canAdd[i]][col] = '-';
            countMAX[canAdd[i]]--;
        }

        for (int i = 0 ; i < canAdd.size() ; ++i)
        {
            if (countMAX[canAdd[i]] == 0)
            {
                std::swap(canAdd[i], canAdd.back());
                canAdd.pop_back(); --i;
                continue;
            }
        }
    }
}

void print()
{
    std::cout << answer << '\n';
    if (reversed)
    {
        for (int i = 1 ; i <= m ; ++i)
        {
            for (int j = 1 ; j <= n ; ++j)
            {
                if (t[j][i] == '-') t[j][i] = '+';
                else t[j][i] = '-';
                std::cout << t[j][i];
            }

            std::cout << '\n';
        }
    } else
    {
        for (int i = 1 ; i <= n ; ++i)
        {
            std::cout << t[i] + 1 << '\n';
        }
    }
}

void input()
{
    std::cin >> n >> m;
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int tests;
int main()
{
    fastIOI();
    std::cin >> tests;

    while (tests--)
    {
        input();
        solve();
        print();
    }


    return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from stones.cpp:5:
stones.cpp: In function 'void solve()':
stones.cpp:67:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   67 |         assert(canAdd.size() >= needed);
      |                ~~~~~~~~~~~~~~^~~~~~~~~
stones.cpp:80:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for (int i = 0 ; i < canAdd.size() ; ++i)
      |                          ~~^~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 10 / 10
• Subtask 3: 16 / 16
• Subtask 4: 11 / 11
• Subtask 5: 15 / 15
• Subtask 6: 31 / 31