oj.uz

Submission #344834

# Submission time Handle Problem Language Result Execution time Memory
344834 2021-01-06T15:48:45 Z darkxeon Red-blue table (IZhO19_stones) C++17
100 / 100
 92 ms 31880 KB 
#include <bits/stdc++.h>
#define sz(x) (long long)(x).size()
 
using namespace std;
 
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
 
const int N = 1e5 + 5, M = 1e6 + 7, SM = 1e3 + 5, logN = 20;
const long long MOD = 1e9 + 7, INF = 1e18 + 9;
const int dx[] = {1, 0, 0, -1, -1, 1, -1, 1};
const int dy[] = {0, 1, -1, 0, -1, 1, 1, -1};
 
void debug() {
	cerr << "\n";
}
template<typename Head, typename... Tail>
void debug(Head a, Tail... b) {
	cerr << a << " ";
	debug(b...);
}
 
void fill(vector<vector<long long>> &a, long long x) {
	long long n = sz(a), m = sz(a[0]);
	for(long long i = 0; i < n; i++) {
		for(long long j = 0; j < m; j++) {
			a[i][j] = x;
		}
	}
}
 
long long div_ceil(long long a, long long b) {
	return (a + b - 1) / b;
}
 
long long calc(vector<vector<long long>> a) {
	long long n = sz(a), m = sz(a[0]);
	vector<long long> rows(n), cols(m);
	for(long long i = 0; i < n; i++) {
		for(long long j = 0; j < m; j++) {
			if(a[i][j] == 1) {
				rows[i]++;
			}
			else {
				cols[j]++;
			}
		}
	}
	long long res = 0;
	for(long long i = 0; i < n; i++) {
		if(rows[i] >= div_ceil(m + 1, 2)) res++;
	}
	
	for(long long j = 0; j < m; j++) {
		if(cols[j] >= div_ceil(n + 1, 2)) res++;
	}
	
	return res;
}
 
void print(vector<vector<long long>> a) {
	long long n = sz(a), m = sz(a[0]);
	for(long long i = 0; i < n; i++) {
		for(long long j = 0; j < m; j++) {
			cout << (a[i][j] ? "+" : "-");
		}
		cout << "\n";
	}
}
 
int main() {
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	long long q; cin >> q;
	
	while(q--) {
		long long n, m; cin >> n >> m;
		
		vector<vector<long long>> grid(n, vector<long long>(m)), ans(n, vector<long long>(m));
		
		vector<long long> rows(n, m), cols(m, n);
			
		fill(grid, 1);
		
		{
			long long last = 0;
			for(long long j = 0; j < m; j++) {
				long long i = last;
				while(cols[j] > (n - 1) / 2) {
					if(rows[i] > div_ceil(m + 1, 2)) {
						grid[i][j] = 0;
						rows[i]--, cols[j]--;
					}
					i++;
					if(i == n) {
						i = 0;
					}
					if(i == last) break;
				}
				last = i;
			}
			
			if(calc(ans) < calc(grid)) {
				ans = grid;
			}
		}
		
		fill(grid, 0);
		rows = vector<long long>(n), cols = vector<long long>(m);
		
		{
			long long last = 0;
			for(long long i = 0; i < n; i++) {
				long long j = last;
				while(rows[i] < div_ceil(m + 1, 2)) {
					if(cols[j] < (n - 1) / 2) {
						grid[i][j] = 1;
						rows[i]++, cols[j]++;
					}
					j++;
					if(j == m) {
						j = 0;
					}
					if(j == last) break;
				}
				last = j;
			}
			
			if(calc(ans) < calc(grid)) {
				ans = grid;
			}
		}
		
		cout << calc(ans) << "\n";
		print(ans);
	}
	
	cout << endl;
	return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory 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

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 4 ms 492 KB Output is correct
4 Correct 7 ms 492 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 1900 KB Output is correct
2 Correct 89 ms 21276 KB Output is correct
3 Correct 74 ms 23300 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2316 KB Output is correct
2 Correct 73 ms 16760 KB Output is correct
3 Correct 72 ms 11300 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 4 ms 492 KB Output is correct
4 Correct 7 ms 492 KB Output is correct
5 Correct 69 ms 1900 KB Output is correct
6 Correct 89 ms 21276 KB Output is correct
7 Correct 74 ms 23300 KB Output is correct
8 Correct 62 ms 2316 KB Output is correct
9 Correct 73 ms 16760 KB Output is correct
10 Correct 72 ms 11300 KB Output is correct
11 Correct 23 ms 620 KB Output is correct
12 Correct 69 ms 14516 KB Output is correct
13 Correct 63 ms 10328 KB Output is correct
14 Correct 51 ms 6520 KB Output is correct
15 Correct 92 ms 31880 KB Output is correct
16 Correct 67 ms 23604 KB Output is correct
17 Correct 29 ms 10604 KB Output is correct