Submission #378635

#	Time	Username	Problem	Language	Result	Execution time	Memory
378635		iris2617	Chessboard (IZhO18_chessboard)	C++14	100 / 100	832 ms	4220 KiB

chessboard

#include<bits/stdc++.h>
#define int long long
#define matsuri pair<int,int>
#define iris 1000000007
using namespace std;

int xx1[100010],yy1[100010],xx2[100010],yy2[100010],n,k;

int cal(int x,int y,int shion)
{
	int a,b,res=0;
	a=x/shion;
	b=y/shion;
	if((a*b)&1)
		res+=shion*shion;
	if(a&1)
	{
		if((b+1)&1)
			res+=shion*(y%shion);
		else
			res-=shion*(y%shion);
	}
	if(b&1)
	{
		if((a+1)&1)
			res+=shion*(x%shion);
		else
			res-=shion*(x%shion);
	}
	if((a+b)&1)
		res-=(x%shion)*(y%shion);
	else
		res+=(x%shion)*(y%shion);
//	cout<<x<<' '<<y<<' '<<shion<<' '<<res<<'\n';
	return res;
}

int sana(int shion)
{
	int a,b,cnt,ouo,i;
	cnt=(n/shion)*(n/shion);
	a=cnt/2*shion*shion;
	b=(cnt+1)/2*shion*shion;
	ouo=0;
	for(i=0;i<k;i++)
	{
		ouo+=cal(xx2[i],yy2[i],shion)-cal(xx1[i]-1,yy2[i],shion)-cal(xx2[i],yy1[i]-1,shion)+cal(xx1[i]-1,yy1[i]-1,shion);
	}
//	cout<<shion<<' '<<a<<' '<<b<<' '<<a+ouo<<' '<<b-ouo<<'\n';
	return min(a+ouo, b-ouo);
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int i,ans=1e18;
	
	cin>>n>>k;
	for(i=0;i<k;i++)
	{
		cin>>xx1[i]>>yy1[i]>>xx2[i]>>yy2[i];
	}
	for(i=1;i<=sqrt(n);i++)
	{
		if(n%i==0)
		{
			ans=min(ans, sana(i));
			if(i>1)
				ans=min(ans, sana(n/i));
		}
	}
	cout<<ans<<'\n';
	
	return 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