Submission #1025763

#TimeUsernameProblemLanguageResultExecution timeMemory
1025763hasan2006Red-blue table (IZhO19_stones)C++17
53 / 100
26 ms11088 KiB
#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]; } l = 1; 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]; } 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 : حسن

Compilation message (stderr)

stones.cpp: In function 'void solve()':
stones.cpp:27:12: warning: unused variable 'q' [-Wunused-variable]
   27 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |            ^
stones.cpp:27:50: warning: unused variable 'k' [-Wunused-variable]
   27 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                  ^
stones.cpp:27:58: warning: unused variable 'mn' [-Wunused-variable]
   27 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                          ^~
stones.cpp:27:69: warning: unused variable 'mx' [-Wunused-variable]
   27 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                                     ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...