oj.uz

Submission #308768

# Submission time Handle Problem Language Result Execution time Memory
308768 2020-10-01T21:53:38 Z nikatamliani Red-blue table (IZhO19_stones) C++14
17 / 100
 2000 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int T = 1;
    cin >> T;
    while(T--) {
        int n, m, cntI = 0, best = 0;
        cin >> n >> m; 
        // bool ans[n + 1][m + 1];
        // memset(ans, 0, sizeof ans);
        // for(int i = 0; i <= n; ++i) {
        //     int sum = i * (m / 2 + 1);
        //     int cnt_less = m - sum % m;
        //     int cnt_more = sum % m;
        //     int less = sum / n;
        //     int more = less + 1; 
        //     int rem = n * m - sum, now = i;
        //     int can = (n - 1) / 2, have = n - can;
        //     sum = max(0, sum - can * m);
        //     now += m - (sum + have - 1) / have;
        //     if(best < now) {
        //         best = now, cntI = i;
        //     }
        // }
        // int prev = 1;
        // for(int i = 1; i <= cntI; ++i) {
        //     int cnt = (m + 1) / 2;
        //     for(int j = prev; cnt--; j = (j == m ? 1 : j + 1)) {
        //         prev = (j == m ? 1 : j + 1);
        //         ans[i][j] = 1;
        //     }
        // }
        // cout << best << '\n';
        // for(int i = 1; i <= n; ++i) {
        //     for(int j = 1; j <= m; ++j) {
        //         if(ans[i][j]) {
        //             cout << '+';
        //         } else {
        //             cout << '-';
        //         }
        //     }
        //     cout << '\n';
        // }
        int p = n * m, real_best = 0;
        for(int mask = 0; mask < (1 << p); ++mask) {
            vector < int > row(n, 0), col(m, 0);
            for(int i = 0; i < p; ++i) {
                if(mask >> i & 1) {
                    ++row[i / m]; --col[i % m];
                } else {
                    --row[i / m]; ++col[i % m]; 
                }
            }
            int cur = 0;
            for(int i = 0; i < n; ++i) {
                cur += row[i] > 0;
            }
            for(int i = 0; i < m; ++i) {
                cur += col[i] > 0;
            }
            real_best = max(real_best, cur);
        }
        cout << real_best << '\n';
        for(int mask = 0; mask < (1 << p); ++mask) {
            vector < int > row(n, 0), col(m, 0);
            for(int i = 0; i < p; ++i) {
                if(mask >> i & 1) {
                    ++row[i / m]; --col[i % m];
                } else {
                    --row[i / m]; ++col[i % m]; 
                }
            }
            int cur = 0;
            for(int i = 0; i < n; ++i) {
                cur += row[i] > 0;
            }
            for(int i = 0; i < m; ++i) {
                cur += col[i] > 0;
            }
            if(cur == real_best) {
                for(int i = 0; i < p; ++i) {
                    if(mask >> i & 1) {
                        cout << "+";
                    } else {
                        cout << "-";
                    }
                    if((i + 1) % m == 0) cout << '\n';
                }
                break;
            }
        }
    }
}

Compilation message

stones.cpp: In function 'int main()':
stones.cpp:7:19: warning: unused variable 'cntI' [-Wunused-variable]
    7 |         int n, m, cntI = 0, best = 0;
      |                   ^~~~
stones.cpp:7:29: warning: unused variable 'best' [-Wunused-variable]
    7 |         int n, m, cntI = 0, best = 0;
      |                             ^~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 13 ms 256 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2071 ms 256 KB Time limit exceeded

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 13 ms 256 KB Output is correct
3 Execution timed out 2071 ms 256 KB Time limit exceeded

Subtask #4
0 / 11.0

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

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2025 ms 368 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 384 KB Output is correct
2 Correct 13 ms 256 KB Output is correct
3 Execution timed out 2071 ms 256 KB Time limit exceeded