oj.uz

Submission #761460

# Submission time Handle Problem Language Result Execution time Memory
761460 2023-06-19T17:20:42 Z NK_ Red-blue table (IZhO19_stones) C++17
100 / 100
 33 ms 2516 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

template<class T> using V = vector<T>;
using str = string;
using T = pair<int, int>;

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

	bool SWAP = 0;
	if (N < M) { swap(N, M); SWAP = 1; }

	// WLOG N > M

	int have = (M - 1) / 2;
	int need = (N / 2) + 1;
	int can = (have * N) / need;
	int ans = can + N;

	V<str> A(N, str(M, '+'));


	priority_queue<T, vector<T>> S;
	for(int i = 0; i < N; i++) S.push(make_pair(have, i));

	for(int c = 0; c < can; c++) {
		V<pair<int, int>> add;

		for(int t = 0; t < need; t++) {
			if (size(S) == 0) assert(false);
			
			int amt, i; tie(amt, i) = S.top(); S.pop();

			A[i][c] = '-'; amt--;
			if (amt > 0) add.push_back(make_pair(amt, i));
		}

		for(auto p : add) S.push(p);
	}

	if (SWAP) {
		V<str> B(M, str(N, '_'));
		for(int r = 0; r < N; r++) for(int c = 0; c < M; c++) {
			B[c][r] = '+' + '-' - A[r][c];
		}
		A.swap(B);
		swap(N, M);
	}

	cout << ans << nl;
	for(auto x : A) cout << x << nl;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int T; cin >> T;
	while(T--) solve();

    return 0;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1376 KB Output is correct
2 Correct 31 ms 2304 KB Output is correct
3 Correct 28 ms 1868 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1288 KB Output is correct
2 Correct 26 ms 1492 KB Output is correct
3 Correct 24 ms 1360 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 27 ms 1376 KB Output is correct
6 Correct 31 ms 2304 KB Output is correct
7 Correct 28 ms 1868 KB Output is correct
8 Correct 25 ms 1288 KB Output is correct
9 Correct 26 ms 1492 KB Output is correct
10 Correct 24 ms 1360 KB Output is correct
11 Correct 7 ms 468 KB Output is correct
12 Correct 25 ms 1580 KB Output is correct
13 Correct 31 ms 1400 KB Output is correct
14 Correct 20 ms 1276 KB Output is correct
15 Correct 33 ms 2260 KB Output is correct
16 Correct 26 ms 2516 KB Output is correct
17 Correct 11 ms 936 KB Output is correct