oj.uz

Submission #370942

# Submission time Handle Problem Language Result Execution time Memory
370942 2021-02-25T06:22:18 Z fhvirus Red-blue table (IZhO19_stones) C++17
100 / 100
 42 ms 2284 KB 
// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef int64_t ll;
typedef pair<int,int> pii; typedef pair<ll,ll> pll;
#define ff first
#define ss second
#define pb emplace_back
#define FOR(i,n) for(int i=0;i<(n);++i)
#define FOO(i,a,b) for(int i=(a);i<=int(b);++i)
#define OOF(i,a,b) for(int i=(a);i>=int(b);--i)
#define AI(x) (x).begin(),(x).end()
template<class I>bool chmax(I&a,I b){return a<b?(a=b,true):false;}
template<class I>bool chmin(I&a,I b){return b<a?(a=b,true):false;} 
template<class V>void lisan(V&v){sort(AI(v));v.erase(unique(AI(v)),v.end());}
template<class V,class T>int lspos(const V&v,T x){return lower_bound(AI(v),x)-v.begin();}
template<class...T>void RI(T&...t){(...,(cin>>t));}
template<class...T>void PL(T...t){int c=sizeof...(T);if(!c){cout<<'\n';return;}(...,(cout<<t<<(--c?' ':'\n')));}
constexpr inline ll cdiv(ll x,ll m){return x/m+(x%m?(x<0)^(m>0):0);}
constexpr inline ll mpow(ll x,ll e,ll m){ll r=1;for(x%=m;e;e/=2,x=x*x%m)if(e&1)r=r*x%m;return r;}
#ifdef OWO
#define safe cerr<<"\033[1;32m"<<__PRETTY_FUNCTION__<<" - "<<__LINE__<<" JIZZ\033[0m\n"
#define debug(args...) SDF(#args, args)
#define OIU(args...) ostream& operator<<(ostream&O,args)
#define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}
template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}
template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
#else
#pragma GCC optimize("Ofast")
#define safe ((void)0)
#define debug(...) ((void)0)
#endif
constexpr ll inf = 1e9, INF = 4e18;
const int N = 1001;
char a[N][N];
int t, n, m;
int cnt[N];
void solve(){
	cin >> n >> m;

	bool rot = false;
	if(n > m) rot = true, swap(n, m);
	FOR(i,n) FOR(j,m) a[i][j] = '-';

	FOR(j,m) cnt[j] = n;
	int k = 0;
	FOR(i,n){
		FOR(j,m/2+1){
			if(cnt[k] - 1 > n - (cnt[k] - 1)) a[i][k] = '+', --cnt[k];
			++k;
			if(k >= m) k = 0;
		}
	}
	if(rot){
		FOR(i,m) FOR(j,i) swap(a[i][j], a[j][i]);
		FOR(i,m) FOR(j,n) a[i][j] ^= ('+' ^ '-');
		swap(n, m);
	}

	int ans = 0;
	FOR(i,n){
		int sum = 0;
		FOR(j,m) sum += (a[i][j] == '+');
		ans += (sum > m - sum);
	}
	FOR(j,m){
		int sum = 0;
		FOR(i,n) sum += (a[i][j] == '-');
		ans += (sum > n - sum);
	}
	cout << ans << '\n';
	FOR(i,n){
		FOR(j,m) cout << a[i][j];
		cout << '\n';
	}
}
int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> t;
	for(; t; --t) solve();
	return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 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 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 4 ms 492 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1516 KB Output is correct
2 Correct 42 ms 1964 KB Output is correct
3 Correct 38 ms 2156 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1644 KB Output is correct
2 Correct 31 ms 1900 KB Output is correct
3 Correct 28 ms 1772 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 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 4 ms 492 KB Output is correct
5 Correct 39 ms 1516 KB Output is correct
6 Correct 42 ms 1964 KB Output is correct
7 Correct 38 ms 2156 KB Output is correct
8 Correct 38 ms 1644 KB Output is correct
9 Correct 31 ms 1900 KB Output is correct
10 Correct 28 ms 1772 KB Output is correct
11 Correct 10 ms 620 KB Output is correct
12 Correct 34 ms 1896 KB Output is correct
13 Correct 34 ms 2028 KB Output is correct
14 Correct 25 ms 1772 KB Output is correct
15 Correct 37 ms 2284 KB Output is correct
16 Correct 29 ms 1900 KB Output is correct
17 Correct 13 ms 1408 KB Output is correct