제출 #492396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
492396		phamhoanghiep	Chessboard (IZhO18_chessboard)	C++14	0 / 100	77 ms	1208 KiB

chessboard

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> iiii;
const int maxn=1e5+5;
int n,k;
iiii black[maxn];
vector<int> divisors;
pair<ll,ll> calc(int d, iiii x) {
    int cnt_col_0=0;
    int cnt_col_1=0;
    int cnt_row_0=0;
    int cnt_row_1=0;
    int l_col=x.fi.se/d;
    int r_col=x.se.se/d;
    if(l_col==r_col) {
        if(l_col%2) cnt_col_1=r_col-l_col+1;
        else cnt_col_0=r_col-l_col+1;
    }
    else {
        int rem_l_col=d-x.fi.se%d;
        int rem_r_col=x.se.se%d+1;
        //cout<<"rem col l r "<<rem_l_col<<" "<<rem_r_col<<endl;
        if(l_col&1) cnt_col_1+=rem_l_col;
        else cnt_col_0+=rem_l_col;
        if(r_col&1) cnt_col_1+=rem_r_col;
        else cnt_col_0+=rem_r_col;
    }
    //cout<<"cnt_col 0 1 "<<cnt_col_0<<" "<<cnt_col_1<<endl;
    l_col++;
    r_col--;
    if(l_col<=r_col) {
        int diff=(r_col-l_col+1);
        cnt_col_0+=diff*d/2;
        cnt_col_1+=diff*d/2;
        if(diff&1) {
            if(l_col&1) cnt_col_1+=d;
            else cnt_col_0+=d;
        }
    }
    //cout<<"cnt_col 0 1 "<<cnt_col_0<<" "<<cnt_col_1<<endl;
    int l_row=x.fi.fi/d;
    int r_row=x.se.fi/d;
    if(l_row==r_row) {
        if(l_row%2) cnt_row_1=r_row-l_row+1;
        else cnt_row_0=r_row-l_row+1;
    }
    else {
        int rem_l_row=d-x.fi.fi%d;
        int rem_r_row=x.se.fi%d+1;
        if(l_row&1) cnt_row_1+=rem_l_row;
        else cnt_row_0+=rem_l_row;
        if(r_row&1) cnt_row_1+=rem_r_row;
        else cnt_row_0+=rem_r_row;
    }
    //cout<<"cnt_row 0 1 "<<cnt_row_0<<" "<<cnt_row_1<<endl;
    l_row++;
    r_row--;
    if(l_row<=r_row) {
        int diff=(r_row-l_row+1);
        cnt_row_0+=diff*d/2;
        cnt_row_1+=diff*d/2;
        if(diff&1) {
            if(l_row&1) cnt_row_1+=d;
            else cnt_row_0+=d;
        }
    }
    //cout<<"cnt_row 0 1 "<<cnt_row_0<<" "<<cnt_row_1<<endl;
    ll a0=1ll*cnt_col_0*cnt_row_0+1ll*cnt_col_1*cnt_row_1;
    ll a1=1ll*cnt_col_0*cnt_row_1+1ll*cnt_col_1*cnt_row_0;
    //cout<<"a0 a1 = "<<a0<<" "<<a1<<endl;
    return make_pair(a0,a1);
}
ll solve(ll a0, ll a1, int d) {
    int t=n/d;
    ll ans=n*n;
    //cout<<"solve "<<a0<<" "<<a1<<" "<<d<<endl;
    if(t&1) {
        ll c0=1ll*t*t/2+1;
        ll c1=1ll*t*t/2+1;
        c0*=1ll*d*d;
        c1*=1ll*d*d;
        ans=min(a0+c1-a1,a1+c0-a0);
        swap(c0,c1);
        ans=min(ans,a0+c1-a1);
        ans=min(ans,a1+c0-a0);
        return ans;
    }
    else {
        ll c0=1ll*t*t/2;
        ll c1=1ll*t*t/2;
        c0*=1ll*d*d;
        c1*=1ll*d*d;
        return min(a0+c1-a1,a1+c0-a0);
    }
}
signed main() {
    cin>>n>>k;
    for(int i=1 ; i<=k ; i++) {
        cin>>black[i].fi.fi>>black[i].fi.se>>black[i].se.fi>>black[i].se.se;
        black[i].fi.fi--; black[i].fi.se--;
        black[i].se.fi--; black[i].se.se--;
    }
    for(int i=1 ; i<n ; i++) {
        if(n%i==0) {
            divisors.push_back(i);
        }
    }
    ll ans=n*n;
    for(int u: divisors) {
        //cout<<"u = "<<u<<endl;
        ll a0=0;
        ll a1=0;
        for(int i=1 ; i<=k ; i++) {
            pair<ll,ll> tmp=calc(u,black[i]);
            a0+=tmp.fi;
            a1+=tmp.se;
        }
        ans=min(ans,solve(a0,a1,u));
    }
    cout<<ans;
}

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