oj.uz

Submission #502632

# Submission time Handle Problem Language Result Execution time Memory
502632 2022-01-06T11:04:52 Z stanislavpolyn Red-blue table (IZhO19_stones) C++17
100 / 100
 1169 ms 2180 KB 
#include <bits/stdc++.h>

#define fr(i, a, b) for(int i = (a); i <= (b); ++i)
#define rf(i, a, b) for(int i = (a); i >= (b); --i)
#define fe(x, y) for(auto& x : y)

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pw(x) (1LL << (x))

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key

template<typename T>
bool umn(T& a, T b) { return (a > b ? (a = b, 1) : 0); }
template<typename T>
bool umx(T& a, T b) { return (a < b ? (a = b, 1) : 0); }

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename T>
using ve = vector<T>;

const int N = 1e3 + 5;

int n, m;
char a[N][N];
int cntR[N];
int cntB[N];

int solve(int n, int m, int R = 1e6) {
    fr(i, 1, n) cntR[i] = 0;
    fr(i, 1, m) cntB[i] = n;

    int needR = m / 2 + 1;
    int needB = n / 2 + 1;

    fr(i, 1, n) {
        fr(j, 1, m) {
            a[i][j] = '.';
        }
    }


    int have = m;

    int best = have;
    int bestR = 0;

    fr(i, 1, min(n, R)) {
        fr(T, 1, needR) {
            int mx = -1e9;
            int mxi = -1;
            fr(j, 1, m) {
                if(a[i][j] != 'R' && umx(mx, cntB[j])) {
                    mxi = j;
                }
            }
            cntB[mxi]--;
            if(cntB[mxi] < needB) have--;
            a[i][mxi] = 'R';
        }

        if(umx(best, i + have)) {
            bestR = i;
        }
    }

    fr(i, 1, n) {
        fr(j, 1, m) {
            if(a[i][j] != 'R') {
                a[i][j] = 'B';
            }
        }
    }

    fr(i, bestR + 1, n) {
        fr(j, 1, m) {
            a[i][j] = 'B';
        }
    }

    return best;
}

void solve() {
    cin >> n >> m;

    int score1 = 0;
    int score2 = 0;
    score1 = solve(n, m);
    score2 = solve(m, n);

    if(score1 > score2) {
        cout << solve(n, m) << "\n";
        fr(i, 1, n) {
            fr(j, 1, m) {
                cout << (a[i][j] == 'R' ? '+' : '-');
            }
            cout << "\n";
        }
        return;
    }

    cout << solve(m, n) << "\n";
    fr(i, 1, n) {
        fr(j, 1, m) {
            cout << (a[j][i] == 'R' ? '-' : '+');
        }
        cout << "\n";
    }
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
#else
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
#endif

//    int n, m;
//    cin >> n >> m;
//
////    cout << solve(n, m, n) << "\n";
//////
//    int mx = -1e9;
//    int mxi;
//    fr(i, 0, n) {
////        cout << solve(n, m, i) << " " << i << "\n";
//        if(umx(mx, solve(n, m, i))) {
//            mxi = i;
//        }
//    }
//    cout << mxi << "\n";
//
//    return 0;
//
//    fr(i, 0, n) {
//        cout << solve(n, m, i) << "\n";
//    }
//
//    return 0;

    int t;
    cin >> t;

    while(t--) {
        solve();
    }

    return 0;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 1428 KB Output is correct
2 Correct 1027 ms 2076 KB Output is correct
3 Correct 937 ms 2008 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 1364 KB Output is correct
2 Correct 631 ms 1760 KB Output is correct
3 Correct 550 ms 1624 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 4 ms 332 KB Output is correct
5 Correct 161 ms 1428 KB Output is correct
6 Correct 1027 ms 2076 KB Output is correct
7 Correct 937 ms 2008 KB Output is correct
8 Correct 218 ms 1364 KB Output is correct
9 Correct 631 ms 1760 KB Output is correct
10 Correct 550 ms 1624 KB Output is correct
11 Correct 25 ms 580 KB Output is correct
12 Correct 668 ms 1824 KB Output is correct
13 Correct 662 ms 2008 KB Output is correct
14 Correct 499 ms 1660 KB Output is correct
15 Correct 1169 ms 2180 KB Output is correct
16 Correct 862 ms 1848 KB Output is correct
17 Correct 232 ms 1228 KB Output is correct