oj.uz

Submission #344833

# Submission time Handle Problem Language Result Execution time Memory
344833 2021-01-06T15:47:58 Z darkxeon Red-blue table (IZhO19_stones) C++17
100 / 100
 90 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);
			
		fill(grid, 1);
		
		{
			long long last = 0;
			for(long long j = 0; j < m; j++) {
				long long i = last, cnt = n / 2 + 1;
				while(cnt) {
					if(rows[i] > m / 2 + 1) {
						grid[i][j] = 0;
						rows[i]--, cnt--;
					}
					i++;
					if(i == n) {
						i = 0;
					}
					if(i == last) {
						break;
					}
				}
				if(!cnt) {
					last = i;
				}
				else {
					break;
				}
			}
			
			if(calc(ans) < calc(grid)) {
				ans = grid;
			}
		}
		
		vector<long long> cols(m, n);
		
		fill(grid, 0);
		
		{
			long long last = 0;
			for(long long i = 0; i < n; i++) {
				long long j = last, cnt = m / 2 + 1;
				while(cnt > 0) {
					if(cols[j] > n / 2 + 1) {
						grid[i][j] = 1;
						cols[j]--, cnt--;
					}
					j++;
					if(j == m) {
						j = 0;
					}
					if(j == last) {
						break;
					}
				}
				if(!cnt) {
					last = j;
				}
				else {
					break;
				}
			}
			
			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 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 1836 KB Output is correct
2 Correct 80 ms 21280 KB Output is correct
3 Correct 72 ms 23244 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 2264 KB Output is correct
2 Correct 67 ms 16808 KB Output is correct
3 Correct 63 ms 11064 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 7 ms 504 KB Output is correct
5 Correct 65 ms 1836 KB Output is correct
6 Correct 80 ms 21280 KB Output is correct
7 Correct 72 ms 23244 KB Output is correct
8 Correct 58 ms 2264 KB Output is correct
9 Correct 67 ms 16808 KB Output is correct
10 Correct 63 ms 11064 KB Output is correct
11 Correct 22 ms 768 KB Output is correct
12 Correct 67 ms 14500 KB Output is correct
13 Correct 63 ms 10416 KB Output is correct
14 Correct 54 ms 6524 KB Output is correct
15 Correct 90 ms 31880 KB Output is correct
16 Correct 65 ms 23732 KB Output is correct
17 Correct 28 ms 10604 KB Output is correct