oj.uz

Submission #170871

# Submission time Handle Problem Language Result Execution time Memory
170871 2019-12-26T16:01:58 Z Trickster Red-blue table (IZhO19_stones) C++14
100 / 100
 98 ms 2296 KB 
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>

#define N 1010
#define ff first
#define ss second
#define ll long long
#define pb push_back
#define mod 1000000007
#define pii pair <int, int>

using namespace std;

int t;
int n, m;
char v[N][N];

int main()
{
	cin >> t;
	
	while(t--) {
		cin >> n >> m;
		
		for(int i = 1; i <= n; i++)
			for(int h = 1; h <= m; h++)
				v[i][h] = (n > m ? '+' : '-');
		
		if(n <= m) {
			priority_queue <pii, vector <pii>, greater<pii>> Q;
			
			for(int i = 1; i <= m; i++) Q.push({0, i});
			
			int li = m/2 + 1;
			int sz = n/2 - (n%2 == 0 ? 1 : 0);
			for(int i = 1; i <= n; i++) {
				vector <pii> A;
				
				for(int h = 1; h <= li; h++) {
					pii x = Q.top();
					Q.pop();
					
					if(x.ff == sz) break;
					
					A.pb(x);
					
					if(Q.empty()) break;
				}
				
				if(A.size() < li) break;
				
				for(auto h: A) v[i][h.ss] = '+', Q.push({h.ff+1, h.ss});
			}
		}
		else {
			priority_queue <pii, vector <pii>, greater<pii>> Q;
			
			for(int i = 1; i <= n; i++) Q.push({0, i});
			
			int li = n/2 + 1;
			int sz = m/2 - (m%2 == 0 ? 1 : 0);
			for(int i = 1; i <= m; i++) {
				vector <pii> A;
				
				for(int h = 1; h <= li; h++) {
					pii x = Q.top();
					Q.pop();
					
					if(x.ff == sz) break;
					
					A.pb(x);
					
					if(Q.empty()) break;
				}
				
				if(A.size() < li) break;
				
				for(auto h: A) v[h.ss][i] = '-', Q.push({h.ff+1, h.ss});
			}
		}
		
		int ans = 0;
		for(int i = 1; i <= n; i++) {
			int sum = 0;
			
			for(int h = 1; h <= m; h++)
				sum += (v[i][h] == '+' ? 1 : 0);
			
			if(sum > m/2) ans++;
		}
		for(int i = 1; i <= m; i++) {
			int sum = 0;
			
			for(int h = 1; h <= n; h++)
				sum += (v[h][i] == '-' ? 1 : 0);
			
			if(sum > n/2) ans++;
		}
		
		cout << ans << "\n";
		for(int i = 1; i <= n; i++) {
			for(int h = 1; h <= m; h++)
				cout << v[i][h];
			
			cout << "\n";
		}
	}
}

Compilation message

stones.cpp: In function 'int main()':
stones.cpp:56:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(A.size() < li) break;
        ~~~~~~~~~^~~~
stones.cpp:82:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(A.size() < li) break;
        ~~~~~~~~~^~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 7 ms 376 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 1540 KB Output is correct
2 Correct 85 ms 2092 KB Output is correct
3 Correct 81 ms 2168 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 1528 KB Output is correct
2 Correct 76 ms 1968 KB Output is correct
3 Correct 69 ms 1656 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 84 ms 1540 KB Output is correct
6 Correct 85 ms 2092 KB Output is correct
7 Correct 81 ms 2168 KB Output is correct
8 Correct 82 ms 1528 KB Output is correct
9 Correct 76 ms 1968 KB Output is correct
10 Correct 69 ms 1656 KB Output is correct
11 Correct 23 ms 632 KB Output is correct
12 Correct 74 ms 1964 KB Output is correct
13 Correct 77 ms 2060 KB Output is correct
14 Correct 57 ms 1756 KB Output is correct
15 Correct 98 ms 2296 KB Output is correct
16 Correct 71 ms 1912 KB Output is correct
17 Correct 32 ms 1272 KB Output is correct