oj.uz

Submission #269853

# Submission time Handle Problem Language Result Execution time Memory
269853 2020-08-17T10:49:45 Z aZvezda Red-blue table (IZhO19_stones) C++14
100 / 100
 1131 ms 3448 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
typedef unsigned long long ull;
template<class T, class T2> bool chkmax(T &a, const T2 &b) {return (a < b) ? a = b, 1 : 0;}
const int MAX_N = 1e3 + 10;
char tab[MAX_N][MAX_N];
 
int get(int n, int m) {
	int total = n * m;
	int ret = 0, retmask;
	for(int mask = 0; mask < (1 << total); mask ++) {
		for(int j = 0; j < total; j ++) {
			tab[j / m][j % m] = (bool)(mask & (1 << j)); 
		}
		int a = 0;
		for(int i = 0; i < n; i ++) {
			int curr = 0;
			for(int j = 0; j < m; j ++) {
				if(tab[i][j]) {
					curr ++;
				} else {
					curr --;
				}
			}
			if(curr > 0) {
				a ++;
			}
		}
		for(int j = 0; j < m; j ++) {
			int curr = 0;
			for(int i = 0; i < n; i ++) {
				if(tab[i][j]) {
					curr --;
				} else {
					curr ++;
				}
			}
			if(curr > 0) {
				a ++;
			}
		}
		if(chkmax(ret, a)) {
			retmask = mask;
		}
	}
	for(int j = 0; j < total; j ++) {
		tab[j / m][j % m] = (bool)(retmask & (1 << j)); 
	}
	cout << n << " " << m << " " << ret << endl;
	for(int i = 0; i < n; i ++) {
		for(int j = 0; j < m; j ++) {
			cout << tab[i][j] << " ";
		}
		cout << endl;
	}
	cout << "!" << endl;
	return ret;
}
 
int cnt[MAX_N];
char ans[MAX_N][MAX_N];
int getFast(int n, int m) {
	bool rev = 0;
	if(n > m) {
		rev = true;
		swap(n, m);
	}
	for(int i = 0; i < m; i ++) {
		cnt[i] = n;
	}
	int ret = max(n, m);
	int halfCnt = (m / 2) + 1;
	int gotten = 0, opti = 0;
	for(int i = 0; i < n; i ++) {
		for(int j = 0; j < m; j ++) {
			ans[i][j] = tab[i][j] = '-';
		}
	}
	for(int i = 0; i < n; i ++) {
		//sort(cnt, cnt + m);
		//reverse(cnt, cnt + m);
		vector<pair<int, int> > cpy;
		for(int j = 0; j < m; j ++) {
			cpy.push_back({-cnt[j], j});
		}
		sort(cpy.begin(), cpy.end());
		for(int j = 0; j < halfCnt; j ++) {
			cnt[cpy[j].second] --;
			ans[i][cpy[j].second] = '+';
		}
		gotten ++;
		int curr = gotten;
		for(int j = 0; j < m; j ++) {
			if(cnt[j] * 2 > n) {
				curr ++;
			}
		}
		if(chkmax(ret, curr)) {
			for(int i = 0; i < n; i ++) {
				for(int j = 0; j < m; j ++) {
					tab[i][j] = ans[i][j];
				}
			}
		}
	}
	if(rev) {
		for(int i = 0; i < n; i ++) {
			for(int j = 0; j < m; j ++) {
				if(tab[i][j] == '-') {
					tab[i][j] = '+';
				} else {
					tab[i][j] = '-';
				}
			}
		}
		for(int i = 0; i < n; i ++) {
			for(int j = 0; j < m; j ++) {
				if(i < j) {
					swap(tab[i][j], tab[j][i]);
				}
			}
		}
		swap(n, m);
	}
	int a = 0;
	for(int i = 0; i < n; i ++) {
		int curr = 0;
		for(int j = 0; j < m; j ++) {
			if(tab[i][j] == '+') {
				curr ++;
			} else {
				curr --;
			}
		}
		if(curr > 0) {
			a ++;
		}
	}
	for(int j = 0; j < m; j ++) {
		int curr = 0;
		for(int i = 0; i < n; i ++) {
			if(tab[i][j] == '+') {
				curr --;
			} else {
				curr ++;
			}
		}
		if(curr > 0) {
			a ++;
		}
	}
	//cout << a << " " << ret << endl; 
	cout << a << endl;
	for(int i = 0; i < n; i ++) {
		for(int j = 0; j < m; j ++) {
			cout << tab[i][j];
		}
		cout << endl;
	}
	//assert(a == ret);
	return ret;
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int t; 
	cin >> t;
	while(t --) {
		int n, m;
		cin >> n >> m;
		getFast(n, m);
	}
}

Compilation message

stones.cpp: In function 'int getFast(int, int)':
stones.cpp:75:18: warning: unused variable 'opti' [-Wunused-variable]
   75 |  int gotten = 0, opti = 0;
      |                  ^~~~
stones.cpp: In function 'int get(int, int)':
stones.cpp:49:23: warning: 'retmask' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |   tab[j / m][j % m] = (bool)(retmask & (1 << j));
      |                       ^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 1588 KB Output is correct
2 Correct 692 ms 2800 KB Output is correct
3 Correct 670 ms 2940 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 1784 KB Output is correct
2 Correct 600 ms 2680 KB Output is correct
3 Correct 475 ms 2244 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 131 ms 1588 KB Output is correct
6 Correct 692 ms 2800 KB Output is correct
7 Correct 670 ms 2940 KB Output is correct
8 Correct 196 ms 1784 KB Output is correct
9 Correct 600 ms 2680 KB Output is correct
10 Correct 475 ms 2244 KB Output is correct
11 Correct 23 ms 640 KB Output is correct
12 Correct 435 ms 2552 KB Output is correct
13 Correct 329 ms 2552 KB Output is correct
14 Correct 215 ms 2168 KB Output is correct
15 Correct 1131 ms 3448 KB Output is correct
16 Correct 687 ms 2680 KB Output is correct
17 Correct 202 ms 1788 KB Output is correct