| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1025863 | 2024-07-17T10:51:39 Z | hasan2006 | Red-blue table (IZhO19_stones) | C++17 | 27 ms | 14428 KB |
#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] , ans[N][N] ;
int solve(ll n , ll m)
{
ll q , i , j ,l ,r , x , y , s = 0 , f , k , mn = 1e18, mx = 0 ;
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 < min(m + 1, 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];
}
/*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 > m || 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;
}
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];
}*/
return s;
}
int main(){
TL;
int t = 1;
cin>>t;
while(t--)
{
ll n , m;
cin>>n>>m;
ll s = solve(n , m);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
ans[i][j] = 1 - a[i][j];
ll f = solve(m , n);
if(f >= s){
s = f;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
ans[i][j] = a[j][i];
}
cout<<s<<"\n";
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++)
cout<<(ans[i][j] == 1 ? "+" : "-");
cout<<"\n";
}
}
}
// Author : حسن
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 4444 KB | Output is correct |
| 2 | Correct | 0 ms | 4444 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 6748 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 4444 KB | Output is correct |
| 2 | Correct | 0 ms | 4444 KB | Output is correct |
| 3 | Correct | 2 ms | 6748 KB | Output is correct |
| 4 | Incorrect | 3 ms | 6748 KB | Wrong answer in test 38 5: 40 < 41 |
| 5 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 24 ms | 9816 KB | Output is correct |
| 2 | Correct | 23 ms | 13900 KB | Output is correct |
| 3 | Correct | 27 ms | 14428 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 23 ms | 11864 KB | Wrong answer in test 6 6: 8 < 9 |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 4444 KB | Output is correct |
| 2 | Correct | 0 ms | 4444 KB | Output is correct |
| 3 | Correct | 2 ms | 6748 KB | Output is correct |
| 4 | Incorrect | 3 ms | 6748 KB | Wrong answer in test 38 5: 40 < 41 |
| 5 | Halted | 0 ms | 0 KB | - |