oj.uz

Submission #1117337

# Submission time Handle Problem Language Result Execution time Memory
1117337 2024-11-23T10:38:57 Z KK_1729 Red-blue table (IZhO19_stones) C++17
100 / 100
 71 ms 17152 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<pair<int, int>> a){
    for (auto x: a) cout << x.second << " ";
    cout << endl;
}

void solve(){
    int N, M; cin >> N >> M;
    int n = N; int m = M;

    if (n > m) swap(m, n); // ensures m >= n

    int ans = m;

    multiset<pair<int, int>> s;
    FOR(i,0,m) s.insert({0, i});

    int k = (n+1)/2 - 1;
    int l = (m)/2+1;
    // cout << k << l << endl;
    vector<vector<pair<int, int>>> o;
    FOR(i,0,n){
        vector<pair<int, int>> u;
        FOR(j,0,l){
            auto x = s.begin();
            u.pb(*x);
            s.erase(x);
        }
        
        bool done = false;
        for (auto x: u){
            if (x.first >= k) done = true;
        }
        
        if (done) break;
        o.pb(u);
        // printVector(u);
        ans++;
        for (auto x: u){
            s.insert({x.first+1, x.second});
        }
    }

    cout << ans << endl;
    // cout << o.size() << endl;
    if (N <= M){
        // cout << "a" << endl;
        vector<vector<int>> grid(N, vector<int>(M, 1));
        int i = 0;
        for (auto x: o){
            for (auto item: x){
                // cout << item.second << " ";
                grid[i][item.second] = 0;
            }
            // cout << endl;
            i++;
        }
        FOR(i,0,N){
            FOR(j,0,M){
                if (grid[i][j]) cout << "-";
                else cout << "+";
                
            }
            cout << endl;
        }
    }else{
        vector<vector<int>> grid(N, vector<int>(M, 0));
        int i = 0;
        for (auto x: o){
            
            for (auto item: x){
                grid[item.second][i] = 1;
            }
            i++;
        }
        FOR(i,0,N){
            FOR(j,0,M){
                if (grid[i][j]) cout << "-";
                else cout << "+";
                
            }
            cout << endl;
        }
    }

}
int32_t main(){
    
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int t = 1; cin >> t;
    while (t--) solve();
}

Subtask #1
17.0 / 17.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 1784 KB Output is correct
2 Correct 64 ms 11596 KB Output is correct
3 Correct 65 ms 12516 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 1864 KB Output is correct
2 Correct 60 ms 9080 KB Output is correct
3 Correct 55 ms 6228 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 3 ms 336 KB Output is correct
5 Correct 53 ms 1784 KB Output is correct
6 Correct 64 ms 11596 KB Output is correct
7 Correct 65 ms 12516 KB Output is correct
8 Correct 56 ms 1864 KB Output is correct
9 Correct 60 ms 9080 KB Output is correct
10 Correct 55 ms 6228 KB Output is correct
11 Correct 12 ms 592 KB Output is correct
12 Correct 59 ms 8016 KB Output is correct
13 Correct 64 ms 5896 KB Output is correct
14 Correct 59 ms 3664 KB Output is correct
15 Correct 71 ms 17152 KB Output is correct
16 Correct 57 ms 12676 KB Output is correct
17 Correct 31 ms 5712 KB Output is correct