oj.uz

답안 #992741

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
992741 2024-06-05T06:41:07 Z NValchanov Red-blue table (IZhO19_stones) C++17
17 / 100
 2000 ms 600 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 solve(int row, int col)
{
    if(row == n + 1 && col == 1)
    {
        check();
        return;
    }

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

    table[row][col] = false;

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

    table[row][col] = true;

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

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();
        ans = 0;
        solve(1, 1);
        print();
    }

    return 0;
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2065 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Execution timed out 2065 ms 348 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2029 ms 600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2037 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Execution timed out 2065 ms 348 KB Time limit exceeded
4 Halted 0 ms 0 KB -