oj.uz

Submission #992748

# Submission time Handle Problem Language Result Execution time Memory
992748 2024-06-05T06:51:34 Z NValchanov Red-blue table (IZhO19_stones) C++17
28 / 100
 2000 ms 1368 KB 
#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long ll;

const int MAXN = 1e3 + 10;

int n, m;
bool table[MAXN][MAXN];
bool ans_table[MAXN][MAXN];
int ans;

void read()
{
    cin >> n >> m;
}

void check()
{
    int a = 0;
    for(int i = 1; i <= n; i++)
    {
        int cntr = 0;
        int cntb = 0;

        for(int j = 1; j <= m; j++)
        {
            cntr += (table[i][j]);
            cntb += (!table[i][j]);
        }

        assert(cntr + cntb == m);

        if(cntr > cntb)
            a++;
    }

    int b = 0;
    for(int j = 1; j <= m; j++)
    {
        int cntr = 0;
        int cntb = 0;

        for(int i = 1; i <= n; i++)
        {
            cntr += (table[i][j]);
            cntb += (!table[i][j]);
        }

        assert(cntr + cntb == n);

        if(cntb > cntr)
            b++;
    }

    if(ans < a + b)
    {
        ans = a + b;

        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                ans_table[i][j] = table[i][j];
            }
        }
    }
}

void bruteforce(int row, int col)
{
    if(row == n + 1 && col == 1)
    {
        check();
        return;
    }

    ///cout << "State : " << row << " : " << col << endl;

    table[row][col] = false;

    if(col == m)
        bruteforce(row + 1, 1);
    else
        bruteforce(row, col + 1);

    table[row][col] = true;

    if(col == m)
        bruteforce(row + 1, 1);
    else
        bruteforce(row, col + 1);    
}

void solve_odd()
{
    int rows = n - 1;
    int cols = m - 1;

    if(rows + cols < n)
    {
        cout << n << endl;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                cout << "+";
            }
            cout << endl;
        }
    }
    else if(rows + cols < m)
    {
        cout << m << endl;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                cout << "-";
            }
            cout << endl;
        }
    }
    else
    {
        cout << rows + cols << endl;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(i < rows && j < cols)
                {
                    if((i + j) % 2 == 0)
                    {
                        cout << "-";
                    }
                    else
                    {
                        cout << "+";
                    }
                }
                else if(i < rows)
                {
                    cout << "+";
                }
                else
                {
                    cout << "-";
                }
            }
            cout << endl;
        }
    }
}

void print()
{
    cout << ans << endl;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cout << (ans_table[i][j] ? '+' : '-');
        }
        cout << endl;
    }
}

int main()
{
    // #ifdef ONLINE_JUDGE
    //     freopen(".in", "r", stdin);
    //     freopen(".out", "w", stdout);
    // #endif

    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    cin >> t;
    while(t--)
    {
        read();

        if(n % 2 == 1 && m % 2 == 1)
        {
            solve_odd();
        }
        else
        {
            ans = 0;
            bruteforce(1, 1);
            print();
        } 
    }

    return 0;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 3 ms 476 KB Output is correct
3 Execution timed out 2080 ms 348 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1368 KB Output is correct
2 Correct 14 ms 1112 KB Output is correct
3 Correct 14 ms 1120 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2068 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 3 ms 476 KB Output is correct
3 Execution timed out 2080 ms 348 KB Time limit exceeded
4 Halted 0 ms 0 KB -