oj.uz

답안 #342542

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
342542 2021-01-02T10:48:53 Z dxz05 Red-blue table (IZhO19_stones) C++14
100 / 100
 104 ms 3476 KB 
//#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << "[" << H << "]";
    debug_out(T...);
}

#ifdef dddxxz
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SZ(s) ((int)s.size())

clock_t startTime;

double getCurrentTime() {
    return (double) (clock() - startTime) / CLOCKS_PER_SEC;
}

typedef long long ll;
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const double eps = 0.00001;
const int MOD = 1e9 + 7;
const int INF = 1000000101;
const long long LLINF = 1223372000000000555;
const int N = 2e6 + 4e4;
const int M = 1234;
const int LOG = 19;

int calc(vector<vector<char>> &v) {
    int n = v.size(), m = v[0].size();
    int res = 0;
    for (int i = 0; i < n; i++) {
        int x = 0, y = 0;
        for (int j = 0; j < m; j++) {
            if (v[i][j] == '+') x++;
            else
                y++;
        }
        if (x > y) res++;
    }
    for (int j = 0; j < m; j++) {
        int x = 0, y = 0;
        for (int i = 0; i < n; i++) {
            if (v[i][j] == '-') x++;
            else
                y++;
        }
        if (x > y) res++;
    }

    return res;
}

void stress(int n, int m) {
    vector<vector<char>> ans;
    int best = 0;

    for (int mask = 0; mask < (1 << (n * m)); mask++) {
        vector<vector<char>> v(n);
        for (int i = 0; i < n; i++) {
            v[i].resize(m);
            ll cur = mask >> (m * i);
            for (int j = 0; j < m; j++) {
                if (cur & (1 << j)) v[i][j] = '+';
                else
                    v[i][j] = '-';
            }
        }

        if (calc(v) > best) best = calc(v), ans = v;
    }

    cout << "Stress-Test begin:\n";

    cout << best << endl;
    for (auto &v : ans) {
        for (auto &x : v) cout << x;
        cout << endl;
    }

    cout << "Stress-Test end.\n\n";

}

void solve(int TC) {
    int n, m;
    cin >> n >> m;

    int best = 0;
    vector<vector<char>> ans(n, vector<char>(m, '-'));
    vector<vector<char>> ans2(n, vector<char>(m, '+'));

    if (calc(ans) < calc(ans2)) swap(ans, ans2);
    best = calc(ans);

    if (n <= m) {
        vector<vector<char>> v(n, vector<char>(m, '-'));
        vector<int> cnt(m, 0);
        int mx = 0;
        for (int i = 0; i < n; i++) {
            int x = 0;
            for (int j = 0; j < m; j++) {
                if (x + x > m) break;
                if (cnt[j] < mx) {
                    cnt[j]++;
                    x++;
                    v[i][j] = '+';
                }
            }

            if (x + x <= m) {
                for (int j = 0; j < m; j++) {
                    if (x + x > m) break;
                    if (cnt[j] == mx) {
                        cnt[j]++;
                        x++;
                        v[i][j] = '+';
                    }
                }
                mx++;
            }

            int A = i + 1, B = 0;
            for (int j = 0; j < m; j++){
                if ((n - cnt[j]) > cnt[j]) B++;
            }

            if (A + B > best){
                best = A + B;
                ans = v;
            }

        }

    } else {
        vector<vector<char>> v(n, vector<char>(m, '+'));
        vector<int> cnt(n, 0);
        int mx = 0;
        for (int j = 0; j < m; j++) {
            int x = 0;
            for (int i = 0; i < n; i++) {
                if (x + x > n) break;
                if (cnt[i] < mx) {
                    cnt[i]++;
                    x++;
                    v[i][j] = '-';
                }
            }

            if (x + x <= n) {
                for (int i = 0; i < n; i++) {
                    if (x + x > n) break;
                    if (cnt[i] == mx) {
                        cnt[i]++;
                        x++;
                        v[i][j] = '-';
                    }
                }
                mx++;
            }

            int A = 0, B = j + 1;
            for (int i = 0; i < n; i++){
                if ((m - cnt[i]) > cnt[i]) A++;
            }

            if (A + B > best){
                best = A + B;
                ans = v;
            }

        }

    }

    //stress(n, m);

    assert(best == calc(ans));

    cout << best << endl;

    for (auto &v : ans) {
        for (auto &x : v) cout << x;
        cout << endl;
    }

}

int main() {
    startTime = clock();
    ios_base::sync_with_stdio(false);

    bool llololcal = false;
#ifdef dddxxz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    llololcal = true;
#endif

    int TC = 1;
    cin >> TC;

    for (int test = 1; test <= TC; test++) {
        debug(test);
        solve(test);
    }

    if (llololcal) cerr << endl << "Time: " << getCurrentTime() * 1000 << " ms" << endl;

    return 0;
}

Compilation message

stones.cpp: In function 'int main()':
stones.cpp:18:20: warning: statement has no effect [-Wunused-value]
   18 | #define debug(...) 42
      |                    ^~
stones.cpp:214:9: note: in expansion of macro 'debug'
  214 |         debug(test);
      |         ^~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 364 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 11 ms 364 KB Output is correct
4 Correct 20 ms 492 KB Output is correct

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 1516 KB Output is correct
2 Correct 73 ms 2780 KB Output is correct
3 Correct 77 ms 2836 KB Output is correct

Subtask #5
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 1516 KB Output is correct
2 Correct 66 ms 2408 KB Output is correct
3 Correct 58 ms 1920 KB Output is correct

Subtask #6
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 11 ms 364 KB Output is correct
4 Correct 20 ms 492 KB Output is correct
5 Correct 104 ms 1516 KB Output is correct
6 Correct 73 ms 2780 KB Output is correct
7 Correct 77 ms 2836 KB Output is correct
8 Correct 81 ms 1516 KB Output is correct
9 Correct 66 ms 2408 KB Output is correct
10 Correct 58 ms 1920 KB Output is correct
11 Correct 49 ms 648 KB Output is correct
12 Correct 61 ms 2168 KB Output is correct
13 Correct 68 ms 2016 KB Output is correct
14 Correct 43 ms 1568 KB Output is correct
15 Correct 99 ms 3476 KB Output is correct
16 Correct 64 ms 2712 KB Output is correct
17 Correct 25 ms 1444 KB Output is correct