oj.uz

Submission #910248

# Submission time Handle Problem Language Result Execution time Memory
910248 2024-01-18T03:01:19 Z daoquanglinh2007 Red-blue table (IZhO19_stones) C++17
100 / 100
 52 ms 2388 KB 
#include <bits/stdc++.h>
using namespace std;

#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair

const int NM = 1000;

int T, N, M, ans;
char a[NM+5][NM+5];
priority_queue <pii> Q;
vector <pii> v;

void build(int k, int l){
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++){
			if (i <= k) a[i][j] = '+'; else a[i][j] = '-';
		}
	while (!Q.empty()) Q.pop();
	for (int i = 1; i <= l; i++) Q.push(mp((N+2)/2-N+k, i));
	for (int i = l+1; i <= N; i++) Q.push(mp(-1, i));
	
	for (int i = 1; i <= k; i++){
		v.clear();
		for (int j = 1; j <= M-(M+2)/2; j++){
			v.push_back(Q.top());
			Q.pop();
		}
		for (pii P : v) a[i][P.se] = '-';
		for (pii P : v){
			Q.push(mp(P.fi-1, P.se));
		}
	}
}

void solve(){
	cin >> N >> M;
	int bestk = -1, bestl = -1;
	for (int k = 0; k <= N; k++){
		int num = k*(M-(M+2)/2), den = (N+2)/2-N+k, l;
		if (den <= 0) l = M; else l = min(num/den, M);
		if (k+l > bestk+bestl){
			bestk = k;
			bestl = l;
		}
	}
	cout << bestk+bestl << '\n';
	build(bestk, bestl);
	
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= M; j++) cout << a[i][j];
		cout << '\n';
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> T;
	while (T--){
		solve();
	}
	return 0;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1616 KB Output is correct
2 Correct 46 ms 1984 KB Output is correct
3 Correct 42 ms 2056 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1480 KB Output is correct
2 Correct 46 ms 1872 KB Output is correct
3 Correct 42 ms 1584 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 44 ms 1616 KB Output is correct
6 Correct 46 ms 1984 KB Output is correct
7 Correct 42 ms 2056 KB Output is correct
8 Correct 46 ms 1480 KB Output is correct
9 Correct 46 ms 1872 KB Output is correct
10 Correct 42 ms 1584 KB Output is correct
11 Correct 8 ms 600 KB Output is correct
12 Correct 37 ms 1872 KB Output is correct
13 Correct 39 ms 2132 KB Output is correct
14 Correct 30 ms 1616 KB Output is correct
15 Correct 52 ms 2388 KB Output is correct
16 Correct 38 ms 1768 KB Output is correct
17 Correct 16 ms 1372 KB Output is correct