oj.uz

Submission #384828

# Submission time Handle Problem Language Result Execution time Memory
384828 2021-04-02T11:22:24 Z Kalashnikov Red-blue table (IZhO19_stones) C++17
100 / 100
 450 ms 9452 KB 
#include <bits/stdc++.h>
 
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
 
using namespace std;
using ll = long long;
 
const int N = 1000+5 , inf = 2e9 + 7;
const ll INF = 1e18 ,   mod = 1e9+7 , P = 6547;

int a[N][N] , b[N][N];

void solve() {
	int n , m;
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= m; j ++) {
			a[i][j] = -1;
			b[i][j] = 1;
		}
	}
	int ans = m , ans1 = n;
	{
		set<pair<int,int>> st;
		int mx = (n-1)/2;
		for(int i = 1; i <= m; i ++) {
			if(mx)
				st.insert({0 , i});
		}
		int x = m/2+1;
		for(int i = 1; i <= n; i ++) {
			int p = x;
			int ok = 1;
			vector<int> v;
			while(p --) {
				if(st.empty()) {
					ok = 0;
					break;
				}
				pair<int,int> cur = *st.begin();
				v.push_back(cur.S);
				st.erase(cur);
				cur.F ++;
				if(cur.F < mx) {
					st.insert(cur);
				}
			}
			if(ok) {
				for(auto to: v) {
					a[i][to] = 1;
				}
				ans ++;
			}
		}
	}
	{
		set<pair<int,int>> st;
		int mx = (m-1)/2;
		for(int i = 1; i <= n; i ++) {
			if(mx)
				st.insert({0 , i});
		}
		int x = n/2+1;
		for(int i = 1; i <= m; i ++) {
			int p = x;
			int ok = 1;
			vector<int> v;
			while(p --) {
				if(st.empty()) {
					ok = 0;
					break;
				}
				pair<int,int> cur = *st.begin();
				v.push_back(cur.S);
				st.erase(cur);
				cur.F ++;
				if(cur.F < mx) {
					st.insert(cur);
				}
			}
			if(ok) {
				for(auto to: v) {
					b[to][i] = -1;
				}
				ans1 ++;
			}
		}
	}
	if(ans1 > ans) {
		swap(ans1 , ans);
		swap(a , b);
	}
	
	cout << ans << '\n';
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= m; j ++)
			if(a[i][j] == 1) cout << '+';
			else cout << '-';
			
		cout << '\n';
	}
}
/*
*/
main() {
  //  ios;
    int tt = 1;
    cin >> tt;
    while(tt --) {
        solve();
    }
    return 0;
}

Compilation message

stones.cpp:109:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  109 | main() {
      |      ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 12 ms 8172 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 8428 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 12 ms 8172 KB Output is correct
3 Correct 174 ms 8428 KB Output is correct
4 Correct 289 ms 8336 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 9452 KB Output is correct
2 Correct 174 ms 9196 KB Output is correct
3 Correct 170 ms 9196 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 2540 KB Output is correct
2 Correct 159 ms 6892 KB Output is correct
3 Correct 159 ms 5740 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 12 ms 8172 KB Output is correct
3 Correct 174 ms 8428 KB Output is correct
4 Correct 289 ms 8336 KB Output is correct
5 Correct 407 ms 9452 KB Output is correct
6 Correct 174 ms 9196 KB Output is correct
7 Correct 170 ms 9196 KB Output is correct
8 Correct 179 ms 2540 KB Output is correct
9 Correct 159 ms 6892 KB Output is correct
10 Correct 159 ms 5740 KB Output is correct
11 Correct 450 ms 8556 KB Output is correct
12 Correct 157 ms 9068 KB Output is correct
13 Correct 173 ms 9196 KB Output is correct
14 Correct 122 ms 8940 KB Output is correct
15 Correct 202 ms 9324 KB Output is correct
16 Correct 145 ms 7404 KB Output is correct
17 Correct 68 ms 8556 KB Output is correct