Submission #69272

#	Time	Username	Problem	Language	Result	Execution time	Memory
69272		istlemin	Chessboard (IZhO18_chessboard)	C++14	100 / 100	1727 ms	61384 KiB

chessboard

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

ll n,k;

ll ceilDiv(ll a,ll b){
	return a/b + (a%b!=0);
}

ll getNumBlack(ll x1,ll y1,ll x2,ll y2, ll sq){
    ll x12 = ceilDiv(x1,sq);
	ll y12 = ceilDiv(y1,sq);
	ll x22 = x2/sq;
	ll y22 = y2/sq;

    if((x12+y12)%2==0){ //black in left lower corner
        ll r1,r2;
        if(x22<x12){
            r1 = 0;
            r2 = x2-x1;
		} else if((x22-x12+2)%2==1){
            r1 = ((x22-x12)/2+1)*sq;
            r2 = ((x22-x12)/2)*sq + (x2-x22*sq) + (x12*sq-x1);
        } else {
            r1 = (x22-x12)/2*sq + (x2-x22*sq);
            r2 = (x22-x12)/2*sq + (x12*sq-x1);
        }

        ll c1,c2;
        if(y22<y12){
            c1 = 0;
            c2 = y2-y1;
		} else if((y22-y12+2)%2==1){
            c1 = ((y22-y12)/2+1)*sq;
            c2 = ((y22-y12)/2)*sq + (y2-y22*sq) + (y12*sq-y1);
        } else {
            c1 = (y22-y12)/2*sq + (y2-y22*sq);
            c2 = (y22-y12)/2*sq + (y12*sq-y1);
        }
		return r1*c1+r2*c2;
    } else {
		ll r1,r2;
        if(x22<x12){
            r1 = 0;
            r2 = x2-x1;
		} else if((x22-x12+2)%2==1){
            r1 = ((x22-x12)/2+1)*sq;
            r2 = ((x22-x12)/2)*sq + (x2-x22*sq) + (x12*sq-x1);
        } else {
            r1 = (x22-x12)/2*sq + (x2-x22*sq);
            r2 = (x22-x12)/2*sq + (x12*sq-x1);
        }

        ll c1,c2;
		if(y22<y12){
            c1 = 0;
            c2 = y2-y1;
		} else if((y22-y12)%2==1){
            c1 = ((y22-y12)/2+1)*sq;
            c2 = ((y22-y12)/2)*sq + (y2-y22*sq) + (y12*sq-y1);
        } else {
            c1 = (y22-y12)/2*sq + (y2-y22*sq);
            c2 = (y22-y12)/2*sq + (y12*sq-y1);
        }
		return r1*c2+r2*c1;
    }
}

vector<tuple<ll,ll,ll,ll> > v;

ll getCost(ll sq, bool startWhite){
    ll blackToBlack = 0;
    ll blackToWhite = 0;

    ll whiteToWhite, whiteToBlack;

    if((n/sq)%2==1){
		whiteToWhite = ((n/sq)*(n/sq)/2)*sq*sq;
		whiteToBlack = ((n/sq)*(n/sq)/2+1)*sq*sq;
    } else {
		whiteToWhite = ((n/sq)*(n/sq)/2)*sq*sq;
		whiteToBlack = ((n/sq)*(n/sq)/2)*sq*sq;
    }
    if(startWhite) swap(whiteToBlack,whiteToWhite);

    rep(i,0,k){
		ll x1,y1,x2,y2;
		tie(x1,y1,x2,y2) = v[i];
		ll sz = (x2-x1)*(y2-y1);
        ll numBlack = getNumBlack(x1,y1,x2,y2,sq);
        if(startWhite)
			numBlack = sz-numBlack;

		whiteToBlack -= numBlack;
        blackToBlack += numBlack;
		whiteToWhite -= sz-numBlack;
        blackToWhite += sz-numBlack;
    }

    return whiteToBlack + blackToWhite;
}

int main(){
	cin.sync_with_stdio(false);
    cin>>n>>k;
    rep(i,0,k){
		ll x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		--x1;--y1;
        v.emplace_back(x1,y1,x2,y2);
    }

    /*ll numDivs = 0;
    rep(i,1,n)
		if(n%i==0)
			numDivs++;

    cout<<numDivs<<endl;*/

    ll bestCost = 1e18;

    rep(i,1,n){
		if(n%i==0){
			bestCost = min(bestCost,getCost(i,false));
			bestCost = min(bestCost,getCost(i,true));
		}
    }
    cout<<bestCost<<endl;

	//cout<<getNumBlack(3,5,5,7,4)<<endl;
	//return 0;
    /*srand(time(NULL));
    rep(i,0,1000){
		ll x2 = rand()%10+1;
		ll y2 = rand()%10+1;
		ll x1 = rand()%x2;
		ll y1 = rand()%y2;
		cout<<getNumBlack(x1,y1,x2,y2,rand()%10+1)<<endl;
    }*/


    /*ll w = 7;
    ll h = 5;
    rep(i,0,10){
		rep(j,0,10){
			cout<<(getNumBlack(j,i,j+w,i+h,2)==(w*h/2))<<" ";
		}
        cout<<endl;
    }*/
}

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