oj.uz

답안 #342082

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
342082 2021-01-01T10:39:49 Z kekw Red-blue table (IZhO19_stones) C++17
100 / 100
 190 ms 9324 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

#define range(i, n) for (int i = 0; i < (n); ++i)
#define ar array
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()


typedef long long ll;
typedef long double ld;
using namespace std;

//using namespace __gnu_pbds;

const ll INF = 1e18 + 5;
const int INFi = 1e9;
const int maxN = 1e6 + 1500;
const int md2 = 998244353;
const int md = 1e9 + 7;

vector<vector<int>> sol1(int n, int m) {
    vector<vector<int>> res(n, vector<int> (m, 1));
    vector<int> cnt(n, (m - 1) / 2);
    set<pair<int, int>> can;
    range(i, n) if (cnt[i]) can.insert({cnt[i], i});
    for(int j = m - 1; j >= 0; --j) {
        int need = n - (n - 1) / 2;
        while(need && !can.empty()) {
            auto [a, b] = *can.rbegin();
            can.erase({a, b});
            cnt[b]--;
            res[b][j] = 0;
            a--;
            need--;
            if (a) can.insert({a, b});
        }
        if (need) break;
    }
    return res;
}

vector<vector<int>> sol2(int n, int m) {
    vector<vector<int>> res(n, vector<int> (m, 0));
    vector<int> cnt(m, (n - 1) / 2);
    set<pair<int, int>> can;
    range(i, m) if (cnt[i]) can.insert({cnt[i], i});
    for(int j = n - 1; j >= 0; --j) {
        int need = m - (m - 1) / 2;
        while(need && !can.empty()) {
            auto [a, b] = *can.rbegin();
            can.erase({a, b});
            cnt[b]--;
            res[j][b] = 1;
            a--;
            need--;
            if (a) can.insert({a, b});
        }
        if (need) break;
    }
    return res;
}

int cnt(vector<vector<int>> &res) {
    int ans = 0;
    range(i, res.size()) {
        int w = 0;
        range(j, res[i].size()) {
            if (res[i][j]) w++;
        }
        if (w > (int)res[i].size() - w) ans++;
    }
    range(j, res[0].size()) {
        int w = 0;
        range(i, res.size()) {
            if (res[i][j] == 0) w++;
        }
        if (w > (int)res.size() - w) ans++;
    }
    return ans;
}

void print(vector<vector<int>> &res) {
    cout << cnt(res) << '\n';
    range(i, (int)res.size()) {
        range(j, (int)res[i].size()) {
            if (res[i][j]) cout << "+";
            else cout << "-";
        }
        cout << '\n';
    }
}

void solve() {
    int n, m; cin >> n >> m;
    auto A = sol1(n, m);
    auto B = sol2(n, m);
    if (cnt(A) > cnt(B)) {
        print(A);
    } else {
        print(B);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // cout << setprecision(15) << fixed;
    int tests = 1;
    cin >> tests;
    range(_, tests) {
        solve();
    }
    return 0;
}

Compilation message

stones.cpp: In function 'int cnt(std::vector<std::vector<int> >&)':
stones.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define range(i, n) for (int i = 0; i < (n); ++i)
      |                                       ^
stones.cpp:66:5: note: in expansion of macro 'range'
   66 |     range(i, res.size()) {
      |     ^~~~~
stones.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define range(i, n) for (int i = 0; i < (n); ++i)
      |                                       ^
stones.cpp:68:9: note: in expansion of macro 'range'
   68 |         range(j, res[i].size()) {
      |         ^~~~~
stones.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define range(i, n) for (int i = 0; i < (n); ++i)
      |                                       ^
stones.cpp:73:5: note: in expansion of macro 'range'
   73 |     range(j, res[0].size()) {
      |     ^~~~~
stones.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define range(i, n) for (int i = 0; i < (n); ++i)
      |                                       ^
stones.cpp:75:9: note: in expansion of macro 'range'
   75 |         range(i, res.size()) {
      |         ^~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 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 0 ms 364 KB Output is correct
3 Correct 3 ms 364 KB Output is correct
4 Correct 8 ms 492 KB Output is correct

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 169 ms 1516 KB Output is correct
2 Correct 167 ms 6612 KB Output is correct
3 Correct 164 ms 7088 KB Output is correct

Subtask #5
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 1644 KB Output is correct
2 Correct 151 ms 5356 KB Output is correct
3 Correct 137 ms 3728 KB Output is correct

Subtask #6
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 3 ms 364 KB Output is correct
4 Correct 8 ms 492 KB Output is correct
5 Correct 169 ms 1516 KB Output is correct
6 Correct 167 ms 6612 KB Output is correct
7 Correct 164 ms 7088 KB Output is correct
8 Correct 165 ms 1644 KB Output is correct
9 Correct 151 ms 5356 KB Output is correct
10 Correct 137 ms 3728 KB Output is correct
11 Correct 32 ms 620 KB Output is correct
12 Correct 142 ms 4604 KB Output is correct
13 Correct 147 ms 3692 KB Output is correct
14 Correct 108 ms 2664 KB Output is correct
15 Correct 190 ms 9324 KB Output is correct
16 Correct 170 ms 7020 KB Output is correct
17 Correct 60 ms 3308 KB Output is correct