Submission #52041

#	Time	Username	Problem	Language	Result	Execution time	Memory
52041		mrtsima22	Chessboard (IZhO18_chessboard)	C++17	100 / 100	1147 ms	103384 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int lmax=1999999999;
const long long lmx=1999999999999999999;
const int N=200004;
int n, k, x1[N], y11[N], x2[N], y2[N];
LL ans;
int pos;
 
 LL gety(LL y,LL she){
	if(y <= 0) return 0;
	LL res = (y / she) / 2 * she;
	if((y / she) & 1) res += y % she + 1;
	return res;
}
 
 LL getx(LL x,LL she){
	if(x <= 0) return 0;
	LL res = (x / she) / 2 * she;
	if((x / she) & 1) res += x % she + 1;
	return res;
}
 
void solve(int she){
	LL odd = 0, even = 0;
	for(int i = 1,xx,yy; i <= k; i++){
		LL o1 = gety(y2[i], she) - gety(y11[i] - 1, she);
		LL e1 = (y2[i] - y11[i] + 1) - o1;
		LL o2 = getx(x2[i], she) -  getx(x1[i] - 1, she); 
		LL e2 = (x2[i] - x1[i] + 1) - o2;
		xx = x1[i] / she;
		yy = y11[i] / she;
		if(xx & 1) swap(o1,e1);
		if(yy & 1) swap(o2,e2);
		LL od = 0, ev = 0;
		if((xx + yy) & 1){
			od = e1 * e2 + o1 * o2;
		}
		else{
		    od = o1 * e2 + e1 * o2;
		}
		ev = 1LL * (x2[i] - x1[i] + 1) * (y2[i] - y11[i] + 1) - od;
		
		odd += od;
		even += ev;
	}
	LL cnt = 1LL * (n / she) * (n / she);
	LL res = min(cnt / 2 * she * she + even - odd, (cnt + 1) / 2 * she * she + odd - even);
	if(res < ans){
	    pos = she;
		ans = res;
	}
}
int main(){std::ios::sync_with_stdio(false);
cin>>n>>k;
ans=1e18;
for(int i=1;i<=k;i++)
{
	cin>>x1[i]>>y11[i]>>x2[i]>>y2[i];
	x1[i]--;
	y11[i]--;
	x2[i]--;
	y2[i]--;
}
for(int i=1;i*i<=n;i++)
{
	if(n%i==0)
	{
		solve(i);
		if(i>1&&i!=n/i)
		{
			solve(n/i);
		}
	}
}
cout<<ans<<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