oj.uz

답안 #321504

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
321504 2020-11-12T15:30:08 Z ryansee Red-blue table (IZhO19_stones) C++14
100 / 100
 57 ms 2412 KB 
#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

using ll=long long; 
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>; 

#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (200006)
int main() {
	FAST
	ll t;
	cin>>t;
	while(t--){
		ll n, m;
		cin>>n>>m;
		vector<vector<char>> grid(n+1, vector<char>(m+1, '*'));
		auto bstar=[&](ll r,ll c){
			ll pad = n - r;
			ll need = n/2+1;
			need -= pad;
			if(c * need <= r * ((m+1)/2-1)) return 1;
			else return 0;
		};
		spi ans = spi(0, pi(0, 0));
		FOR(j,0,m) {
			ll st=0,en=n+1;
			while(en-st>1) {
				ll mid=(st+en)>>1;
				if(bstar(mid,j)) st=mid;
				else en=mid;
			}
			ans = max(ans, spi(j+st, pi(st, j)));
		}
		cout<<ans.f<<'\n';
		ll give = 1;
		auto betw=[&](ll a,ll x,ll b) {
			if(a>b) return false;
			--a,--x,--b;
			a%=ans.s.s, b%=ans.s.s;
			if(a<=b) return a <= x && x <= b;
			else return a <= x || x <= b;
		};
		FOR(i,1,ans.s.f) {
			ll until = give + (m+1)/2-1 - 1, ass = 0;
			FOR(j,1,m) if(j <= ans.s.s && betw(give, j, until)) {
				grid[i][j] = 'b';
			} else grid[i][j] = 'r', ++ ass;
			assert(ass > m/2);
			give = until + 1;
		}
		FOR(i,ans.s.f+1,n) {
			FOR(j,1,m) grid[i][j]='b';
		}
		FOR(i,1,n) FOR(j,1,m) { cout<<(grid[i][j]=='r'?'+':'-'); if(j==m) cout<<'\n'; }
	}
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 364 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 4 ms 364 KB Output is correct

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 1468 KB Output is correct
2 Correct 46 ms 1772 KB Output is correct
3 Correct 40 ms 1900 KB Output is correct

Subtask #5
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 1388 KB Output is correct
2 Correct 39 ms 1516 KB Output is correct
3 Correct 36 ms 1352 KB Output is correct

Subtask #6
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 4 ms 364 KB Output is correct
5 Correct 57 ms 1468 KB Output is correct
6 Correct 46 ms 1772 KB Output is correct
7 Correct 40 ms 1900 KB Output is correct
8 Correct 46 ms 1388 KB Output is correct
9 Correct 39 ms 1516 KB Output is correct
10 Correct 36 ms 1352 KB Output is correct
11 Correct 11 ms 620 KB Output is correct
12 Correct 36 ms 1580 KB Output is correct
13 Correct 38 ms 1408 KB Output is correct
14 Correct 29 ms 1168 KB Output is correct
15 Correct 47 ms 2412 KB Output is correct
16 Correct 37 ms 1900 KB Output is correct
17 Correct 15 ms 1004 KB Output is correct