Submission #1034412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034412		hasan2006	Chessboard (IZhO18_chessboard)	C++17	100 / 100	663 ms	6232 KiB

chessboard

#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 o){
    ll f = 0 ,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;
        }
    }
    if(f == 1 && k == 1)
        cout<<s<<" "<<ans <<" ";
    ans = (l - ans) * (r - s) +  (ans * s);
    pair<ll,ll>pa = {ans , l * r - ans};
    if(o)
        swap(pa.fi , pa.se);
    return pa;
}

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;
            //cout<<m<<" ";
            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 (stderr)

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

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 23 / 23
• Subtask 6: 30 / 30