oj.uz

Submission #1025833

# Submission time Handle Problem Language Result Execution time Memory
1025833 2024-07-17T10:39:34 Z hasan2006 Red-blue table (IZhO19_stones) C++17
69 / 100
 34 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(mn + 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 = 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];
    }
    return s;
    /*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--)
     {
        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

stones.cpp: In function 'int solve(long long int, long long int)':
stones.cpp:27:9: warning: unused variable 'q' [-Wunused-variable]
   27 |     ll  q , i , j ,l ,r , x , y , s = 0 , f , k ,  mn = 1e18, mx = 0 ;
      |         ^
stones.cpp:27:47: warning: unused variable 'k' [-Wunused-variable]
   27 |     ll  q , i , j ,l ,r , x , y , s = 0 , f , k ,  mn = 1e18, mx = 0 ;
      |                                               ^
stones.cpp:27:63: warning: unused variable 'mx' [-Wunused-variable]
   27 |     ll  q , i , j ,l ,r , x , y , s = 0 , f , k ,  mn = 1e18, mx = 0 ;
      |                                                               ^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6876 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 3 ms 6876 KB Output is correct
4 Correct 4 ms 6748 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9812 KB Output is correct
2 Correct 30 ms 13900 KB Output is correct
3 Correct 30 ms 14428 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 11860 KB Output is correct
2 Correct 29 ms 12996 KB Output is correct
3 Correct 27 ms 12384 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 3 ms 6876 KB Output is correct
4 Correct 4 ms 6748 KB Output is correct
5 Correct 34 ms 9812 KB Output is correct
6 Correct 30 ms 13900 KB Output is correct
7 Correct 30 ms 14428 KB Output is correct
8 Correct 30 ms 11860 KB Output is correct
9 Correct 29 ms 12996 KB Output is correct
10 Correct 27 ms 12384 KB Output is correct
11 Incorrect 10 ms 4956 KB Wrong answer in test 26 8: 30 < 31
12 Halted 0 ms 0 KB -