oj.uz

Submission #761457

# Submission time Handle Problem Language Result Execution time Memory
761457 2023-06-19T17:19:09 Z NK_ Red-blue table (IZhO19_stones) C++17
100 / 100
 46 ms 2524 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;

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;

	// cout << N << " : " << M << endl;
	// cout << have << " - " << need << endl;
	int can = (have * N) / need;
	// cout << have * N << " - " << need << endl;

	int ans = min(M, can) + N; //??????

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

	set<pair<int, int>> S;
	for(int i = 0; i < N; i++) S.insert(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) = *rbegin(S);
			// cout << amt << " " << i << endl;
			S.erase(prev(end(S)));

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

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

	// for(auto x : A) cout << x << nl;

	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;

	auto checker = [&]() {
		int ANS = 0;
		for(int r = 0; r < N; r++) {
			int x = 0;
			for(int c = 0; c < M; c++) x += (A[r][c] == '+');
			if (x > (M - x)) ANS++;
		}

		for(int c = 0; c < M; c++) {
			int x = 0;
			for(int r = 0; r < N; r++) x += (A[r][c] == '-');
			if (x > (N - x)) ANS++;
		}
		// cout << ANS << endl;

		if (ANS != ans) {
			cout << N << " <--> " << M << endl;
			assert(false);
		}
		assert(ANS == ans);
	};

	checker();

}

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 1 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 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1312 KB Output is correct
2 Correct 42 ms 2252 KB Output is correct
3 Correct 38 ms 1888 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1324 KB Output is correct
2 Correct 41 ms 1636 KB Output is correct
3 Correct 36 ms 1356 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 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 39 ms 1312 KB Output is correct
6 Correct 42 ms 2252 KB Output is correct
7 Correct 38 ms 1888 KB Output is correct
8 Correct 36 ms 1324 KB Output is correct
9 Correct 41 ms 1636 KB Output is correct
10 Correct 36 ms 1356 KB Output is correct
11 Correct 8 ms 468 KB Output is correct
12 Correct 35 ms 1484 KB Output is correct
13 Correct 40 ms 1480 KB Output is correct
14 Correct 29 ms 1164 KB Output is correct
15 Correct 46 ms 2300 KB Output is correct
16 Correct 35 ms 2524 KB Output is correct
17 Correct 15 ms 964 KB Output is correct