oj.uz

Submission #883411

# Submission time Handle Problem Language Result Execution time Memory
883411 2023-12-05T09:07:59 Z boris_mihov Red-blue table (IZhO19_stones) C++17
100 / 100
 25 ms 2396 KB 
#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

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.0 / 17.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct

Subtask #3
16.0 / 16.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1344 KB Output is correct
2 Correct 13 ms 1984 KB Output is correct
3 Correct 25 ms 1976 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1372 KB Output is correct
2 Correct 8 ms 1884 KB Output is correct
3 Correct 7 ms 1740 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 15 ms 1344 KB Output is correct
6 Correct 13 ms 1984 KB Output is correct
7 Correct 25 ms 1976 KB Output is correct
8 Correct 9 ms 1372 KB Output is correct
9 Correct 8 ms 1884 KB Output is correct
10 Correct 7 ms 1740 KB Output is correct
11 Correct 4 ms 600 KB Output is correct
12 Correct 19 ms 1628 KB Output is correct
13 Correct 18 ms 1628 KB Output is correct
14 Correct 10 ms 1384 KB Output is correct
15 Correct 10 ms 2396 KB Output is correct
16 Correct 7 ms 1776 KB Output is correct
17 Correct 8 ms 1116 KB Output is correct