Submission #47897

#	Time	Username	Problem	Language	Result	Execution time	Memory
47897		dqhungdl	Chessboard (IZhO18_chessboard)	C++17	100 / 100	1161 ms	49840 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int,int> ii;
int n,k,odd,even;
int64_t res=1e12;
vector<ii> g1[100005],g2[100005];
 
int Cal(int u,int v,int block)
{
	return ((u-1)/block+1+(v-1)/block+1)%2;
}

void Update(int i,int l,int r,int block,int val)
{
	int ll=(l-1)/block+2;
	int rr=(r-1)/block;
	if(ll==rr+2)
	{
		if(Cal(i,l,block)==1)
			odd+=(r-l+1)*val;
		else
			even+=(r-l+1)*val;
		return;
	}
	odd+=(rr-ll+1)/2*block*val;
	even+=(rr-ll+1)/2*block*val;
	if((rr-ll+1)%2==1)
	{
		if(Cal(i,(ll-1)*block+1,block)==1)
			odd+=block*val;
		else
			even+=block*val;
	}
	if(Cal(i,l,block)==1)
		odd+=((ll-1)*block-l+1)*val;
	else
		even+=((ll-1)*block-l+1)*val;
	if(Cal(i,r,block)==1)
		odd+=(r-(rr*block))*val;
	else
		even+=(r-(rr*block))*val;
}
 
void Check(int block)
{
	int64_t sodd=0,seven=0,tmp=n/block,codd,ceven;
	if(tmp%2==0)
		codd=ceven=int64_t(n)*int64_t(n)/int64_t(2);
	else
	{
		ceven=(int64_t(n)*int64_t(n)+int64_t(block)*int64_t(block))/int64_t(2);
		codd=int64_t(n)*int64_t(n)-ceven;
	}
	odd=even=0;
	for(int i=1;i<=n;i++)
	{
		if(i>1&&(i-1)/block+1!=(i-2)/block+1)
			swap(odd,even);
		for(int j=0;j<g1[i].size();j++)
			Update(i,g1[i][j].first,g1[i][j].second,block,1);
		sodd+=odd;
		seven+=even;
		for(int j=0;j<g2[i].size();j++)
			Update(i,g2[i][j].first,g2[i][j].second,block,-1);
	}
	res=min(res,min(codd-sodd+seven,ceven-seven+sodd));
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	//freopen("TEST.INP","r",stdin);
	//freopen("TEST.OUT","w",stdout);
	cin>>n>>k;
	int u1,v1,u2,v2;
	while(k--)
	{
		cin>>u1>>v1>>u2>>v2;
		g1[u1].push_back(ii(v1,v2));
		g2[u2].push_back(ii(v1,v2));
	}
	for(int i=1;i<n;i++)
		if(n%i==0)
			Check(i);
	cout<<res;
}

Compilation message (stderr)

chessboard.cpp: In function 'void Check(int)':
chessboard.cpp:60:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<g1[i].size();j++)
               ~^~~~~~~~~~~~~
chessboard.cpp:64:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<g2[i].size();j++)
               ~^~~~~~~~~~~~~

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