oj.uz

Submission #173538

# Submission time Handle Problem Language Result Execution time Memory
173538 2020-01-04T14:31:06 Z srvlt Red-blue table (IZhO19_stones) C++14
100 / 100
 211 ms 5408 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree <pair <int, int>, null_type, less <pair <int, int> >, rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;

#define ll long long
#define db double
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mp make_pair
#define size(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define low_b lower_bound

#define endl "\n"
//#define int long long

using namespace std;

void dout() {
    cerr << endl;
}
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;

const int N = 1003;
int n, m, a[N][N];
set <pii> c;

void cleanup() {
    c.clear();
}

void solve(int tc) {
    // check for (int i = 0; i < n; j++)

    // 1(+) row, 0(-) col
    memset(a, -1, sizeof(a));
    cin >> n >> m;
    int k, ans = 0;
    pii z;
    if (n <= m) {
        for (int i = 1; i <= m; i++) {
            c.insert({0, i});
        }
        for (int i = 1; i <= n; i++) {
            k = m / 2 + 1;

            int cur = 0;
            while (k--) {
                z = *c.begin();
                if (z.fi == n - (n / 2 + 1)) {
                    break;
                }
                cur++;
                c.erase(c.begin());
                a[i][z.se] = 1;
                z.fi++;
                c.insert(z);
            }
            if (cur == m / 2 + 1) {
                ans++;
            }
            for (int j = 1; j <= m; j++) {
                if (a[i][j] == -1) {
                    a[i][j] = 0;
                }
            }
        }
        for (auto i : c) {
            if (n - i.fi >= n / 2 + 1) {
                ans++;
            }
        }
    }   else {
        for (int i = 1; i <= n; i++) {
            c.insert({0, i});
        }
        for (int i = 1; i <= m; i++) {
            k = n / 2 + 1;

            int cur = 0;
            while (k--) {
                z = *c.begin();
                if (z.fi == m - (m / 2 + 1)) {
                    break;
                }
                cur++;
                c.erase(c.begin());
                a[z.se][i] = 0;
                z.fi++;
                c.insert(z);
            }
            if (cur == n / 2 + 1) {
                ans++;
            }
            for (int j = 1; j <= n; j++) {
                if (a[j][i] == -1) {
                    a[j][i] = 1;
                }
            }
        }
        for (auto i : c) {
            if (m - i.fi >= m / 2 + 1) {
                ans++;
            }
        }
    }

    cout << ans << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j]) {
                cout << '+';
            }   else {
                cout << '-';
            }
        }
        cout << endl;
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int tc = 1;
    cin >> tc;
    for (int i = 0; i < tc; i++) {
        solve(i);
        cleanup();
    }
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4344 KB Output is correct
2 Correct 8 ms 4216 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 4344 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4344 KB Output is correct
2 Correct 8 ms 4216 KB Output is correct
3 Correct 69 ms 4344 KB Output is correct
4 Correct 114 ms 4484 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 5408 KB Output is correct
2 Correct 90 ms 5276 KB Output is correct
3 Correct 87 ms 5248 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 5304 KB Output is correct
2 Correct 78 ms 5220 KB Output is correct
3 Correct 73 ms 5112 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4344 KB Output is correct
2 Correct 8 ms 4216 KB Output is correct
3 Correct 69 ms 4344 KB Output is correct
4 Correct 114 ms 4484 KB Output is correct
5 Correct 171 ms 5408 KB Output is correct
6 Correct 90 ms 5276 KB Output is correct
7 Correct 87 ms 5248 KB Output is correct
8 Correct 115 ms 5304 KB Output is correct
9 Correct 78 ms 5220 KB Output is correct
10 Correct 73 ms 5112 KB Output is correct
11 Correct 211 ms 4712 KB Output is correct
12 Correct 85 ms 5112 KB Output is correct
13 Correct 89 ms 5112 KB Output is correct
14 Correct 61 ms 4984 KB Output is correct
15 Correct 92 ms 5368 KB Output is correct
16 Correct 70 ms 5112 KB Output is correct
17 Correct 36 ms 4728 KB Output is correct