# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1025818 | hasan2006 | Red-blue table (IZhO19_stones) | C++17 | 2028 ms | 7768 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"
const int N = 1e3 + 9 , mod = 1e9 + 7;
int a[N][N] , b[N] , dp[N] , c[N] , d[N][N] ;
void solve()
{
ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
cin>>n>>m;
ll N = n, M = m;
if(n < m)
swap(n , m);
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
a[i][j] = 0 ,b[i] = m , c[j] = 0;
f = n / 2 + 1;
/* x = m / 2 - (m % 2 == 0) , y = 1;
deque<int>v[m * 2 + 1];
for(i = 1; i <= n; i++){
for(j = y; j < y + x; j++)
a[i][j] = 1 , c[j]++ , b[i]-- , v[j].pb(i);
if(c[y] >= f)
y = y + x;
}
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
d[i][j] = a[i][j];
for(i = 1; i <= n; i++)
s += (b[i] > m / 2);
for(i = 1; i <= m; i++)
s += (c[i] > n / 2);
i = 1;
while(x > 0 && y <= m && (y + x - 1) <= m && f > c[y]){
for(j = 1; j <= m; j++)
b[i] -= (d[i][j] == 0) , c[j] += (d[i][j] == 0) , d[i][j] = 1;
l = y;
for(j = 1; j < y; j++)
if(v[j].size() && c[j] > f && v[j].back() > i){
c[j]--;
c[l]++;
d[v[j].back()][j] = 0;
d[v[j].back()][l] = 1;
l++;
v[j].pop_back();
if(l == y + x)
l = y;
}
i++;
}
ll ans = 0;
for(i = 1; i <= n; i++)
ans += (b[i] > m / 2);
for(i = 1; i <= m; i++)
ans += (c[i] > n / 2);
if(ans >= s){
s = ans;
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
a[i][j] = d[i][j];
}*/
for(k = 0; k <= m; k++){
l = 0;
r = f;
while(l != r){
ll mid = (l + r) / 2;
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
d[i][j] = 0 , c[j] = 0 , b[i] = m;
for(i = 1; i <= mid; i++)
for(j = 1; j <= m; j++)
d[i][j] = 1 , c[j]++ , b[i]--;
x = m / 2 - (m % 2 == 0) , y = 1;
for(i = mid + 1; i <= n; i++){
for(j = y; j < min(m + 1 , y + x); j++)
d[i][j] = 1 , c[j]++ , b[i]--;
if(c[y] >= f)
y = y + x;
}
if(y > k || mid == f)
r = mid;
else
l = mid + 1;
}
ll mid = l;
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
d[i][j] = 0 , c[j] = 0 , b[i] = m;
for(i = 1; i <= mid; i++)
for(j = 1; j <= m; j++)
d[i][j] = 1 , c[j]++ , b[i]--;
x = m / 2 - (m % 2 == 0) , y = 1;
for(i = mid + 1; i <= n; i++){
for(j = y; j < min(m + 1 , y + x); j++)
d[i][j] = 1 , c[j]++ , b[i]-- ;
if(c[y] >= f)
y = y + x;
}
ll ans = 0;
for(i = 1; i <= n; i++)
ans += (b[i] > m / 2);
for(i = 1; i <= m; i++)
ans += (c[i] > n / 2);
if(ans >= s){
s = ans;
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
a[i][j] = d[i][j];
}
}
cout<<s<<"\n";
for(i = 1; i <= N; i++){
for(j = 1; j <= M; j++){
x = (N < M ? a[j][i] : 1 - a[i][j]);
cout<<(x == 1 ? "+" : "-");
}
cout<<"\n";
}
}
int main(){
TL;
int t = 1;
cin>>t;
while(t--)
{
solve();
}
}
// Author : حسن
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |