oj.uz

Submission #788779

# Submission time Handle Problem Language Result Execution time Memory
788779 2023-07-20T15:23:15 Z TheOpChicken Red-blue table (IZhO19_stones) C++17
100 / 100
 83 ms 2252 KB 
#include <bits/stdc++.h>
using namespace std;

bool possible(int i, int n, int m, int mid){
	int total = (n-i)*mid + i*min(mid, m-(m/2+1));
	return total >= mid*(n/2+1);
}

int find_can(int i, int n, int m){
	int l = 0, r = m, ans = 0;
	while(l <= r){
		int mid = (l+r)/2;
		if (!possible(i, n, m, mid)) r = mid-1;
		else{
			ans = mid;
			l = mid+1;
		}
	}

	return ans;
}

int main(){
	int t;
	cin >> t;
	while(t--){
		int n, m;
		cin >> n >> m;

		int opt = 0, can = -1;
		for (int i = 0; i <= n; i++){
			int new_can = find_can(i, n, m);
			if (new_can+i > opt+can) opt = i, can = new_can;
		}

		vector<int> count(m, 0);
		vector<vector<char> > grid(n, vector<char>(m, '+'));

		cout << can + opt << endl;
      
		for (int i = 0; i < n; i++){
			int row_need = (i < opt ? m/2+1 : 0);
			multiset<pair<int, int> > ms;
			for (int j = 0; j < can; j++) ms.insert(make_pair(count[j], j));

			for (int j = 0; j < min(can, m-row_need); j++){
				pair<int, int> a = *ms.begin(); ms.erase(ms.begin());
				grid[i][a.second] = '-';
				count[a.second]++;
			}
		}

		for (int i = 0; i < n; i++){
			for (int j = 0; j < m; j++) cout << grid[i][j];
			cout << endl;
		}
	}
}

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 296 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 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 296 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 10 ms 372 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 1268 KB Output is correct
2 Correct 74 ms 1796 KB Output is correct
3 Correct 61 ms 1844 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 1232 KB Output is correct
2 Correct 63 ms 1608 KB Output is correct
3 Correct 57 ms 1384 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 296 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 10 ms 372 KB Output is correct
5 Correct 83 ms 1268 KB Output is correct
6 Correct 74 ms 1796 KB Output is correct
7 Correct 61 ms 1844 KB Output is correct
8 Correct 78 ms 1232 KB Output is correct
9 Correct 63 ms 1608 KB Output is correct
10 Correct 57 ms 1384 KB Output is correct
11 Correct 28 ms 472 KB Output is correct
12 Correct 60 ms 1428 KB Output is correct
13 Correct 59 ms 1340 KB Output is correct
14 Correct 46 ms 1124 KB Output is correct
15 Correct 83 ms 2252 KB Output is correct
16 Correct 60 ms 1720 KB Output is correct
17 Correct 23 ms 944 KB Output is correct