oj.uz

Submission #1034380

# Submission time Handle Problem Language Result Execution time Memory
1034380 2024-07-25T12:57:51 Z hasan2006 Chessboard (IZhO18_chessboard) C++17
0 / 100
 18 ms 3852 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 = 5e5 + 9 , mod = 1e9 + 7;
ll a[N] , b[N] , dp[N] , c[N] , d[N] , X1[N] , X2[N] , Y1[N] , Y2[N];



pair<ll,ll> get(int p , int k ,int f){
    ll x1 = X1[p] - 1 , y1 = Y1[p] - 1 , x2 = X2[p] - 1 , y2 = Y2[p] - 1 , s = 0 , j , ans = 0 , l = x2 - x1 + 1 , r = y2 - y1 + 1;
    if(y1 / k == y2 / k){
        if((y1 / k) % 2 == f)
            s += (y2 - y1 + 1);
    }else {
        if((y1 / k) % 2 == f)
            s += k - (y1 % k);
        y1 += k - (y1 % k);
        if((y2 / k) % 2 == f)
            s += (y2 % k) + 1;
        y2 -= (y2 % k) + 1;
        if(y1 <= y2){
            j = (y2 / k) - (y1 / k) + 1;
            j += ((y1 / k) % 2 == f);
            s += (j / 2) * k;
        }
    }
    if(x1 / k == x2 / k){
        if((x1 / k) % 2 == f)
            ans += (x2 - x1 + 1);
    }else {
        if((x1 / k) % 2 == f)
            ans += k - (x1 % k);
        x1 += k - (x1 % k);
        if((x2 / k) % 2 == f)
            ans += (x2 % k) + 1;
        x2 -= (x2 % k) + 1;
        if(x1 <= x2){
            j = (x2 / k) - (x1 / k) + 1;
            j += ((x1 / k) % 2 == f);
            ans += (j / 2) * k;
        }
    }
    ans = (l - ans) * (r - s) +  (ans * s);
    return {ans , l * r - ans};
}

void solve()
{
    ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
    cin>>n>>k;
    vector<int>v;
    X1[0] = 1 , Y1[0] = 1 , X2[0] = n , Y2[0] = n;
    for(i = 1; i <= k; i++)
        cin>>X1[i]>>Y1[i]>>X2[i]>>Y2[i];
    for(i = 1; i * i <= n; i++)
        if(n % i == 0)
            v.pb(i) , v.pb(n / i);
    for(j = 0; j < 2; j++)
        for(auto l : v){
            ll ans = 0 , s = 0 , m = get(0 , l , j).fi;
            for(i = 1; i <= k;  i++)
                s += get(i , l , j).fi , ans += get(i , l , j).se;
            if(l != n)
                ans += m - s , mn = min(mn , ans);
        }
    cout<<mn<<"\n";
}

int main(){
    TL;
    /*#ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif*/
    int t = 1;
    //cin>>t;
    while(t--)
     {
        solve();
     }
}
// Author : حسن

Compilation message

chessboard.cpp: In function 'void solve()':
chessboard.cpp:66:12: warning: unused variable 'q' [-Wunused-variable]
   66 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |            ^
chessboard.cpp:66:23: warning: unused variable 'l' [-Wunused-variable]
   66 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                       ^
chessboard.cpp:66:26: warning: unused variable 'r' [-Wunused-variable]
   66 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                          ^
chessboard.cpp:66:30: warning: unused variable 'x' [-Wunused-variable]
   66 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                              ^
chessboard.cpp:66:34: warning: unused variable 'y' [-Wunused-variable]
   66 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                  ^
chessboard.cpp:66:38: warning: unused variable 's' [-Wunused-variable]
   66 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                      ^
chessboard.cpp:66:46: warning: unused variable 'f' [-Wunused-variable]
   66 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                              ^
chessboard.cpp:66:54: warning: unused variable 'm' [-Wunused-variable]
   66 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                      ^
chessboard.cpp:66:69: warning: unused variable 'mx' [-Wunused-variable]
   66 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                                     ^~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3852 KB Output is correct
2 Incorrect 5 ms 1116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3852 KB Output is correct
2 Incorrect 5 ms 1116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -