Submission #47892

#	Time	Username	Problem	Language	Result	Execution time	Memory
47892		dqhungdl	Chessboard (IZhO18_chessboard)	C++17	47 / 100	2074 ms	10496 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;

typedef pair<int64_t,int64_t> ii;
int64_t n,k,odd,even,res=1e12;
vector<ii> g1[100005],g2[100005];

void ReadInt(int64_t &number)
{
    number=0;
    int64_t c=getchar();
    while(c<'0'||c>'9')
    	c=getchar();
    for(;('0'<=c&&c<='9');c=getchar())
        number=number*10+c-48;  
}

int64_t Cal(int64_t u,int64_t v,int64_t block)
{
	return ((u-1)/block+1+(v-1)/block+1)%2;
}

void Update(int64_t i,int64_t l,int64_t r,int64_t block,int64_t val)
{
	int64_t ll=(l-1)/block+2;
	int64_t 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,(l-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(int64_t block)
{
	int64_t tmp=n/block;
	int64_t sodd=0,seven=0,codd,ceven;
	if(tmp%2==0)
		codd=ceven=n*n/2;
	else
	{
		ceven=(n*n+block*block)/2;
		codd=n*n-ceven;
	}
	odd=even=0;
	for(int64_t i=1;i<=n;i++)
	{
		for(int64_t j=0;j<g1[i].size();j++)
			Update(i,g1[i][j].first,g1[i][j].second,block,1);
		sodd+=odd;
		seven+=even;
		for(int64_t 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);
	ReadInt(n);
	ReadInt(k);
	int64_t u1,v1,u2,v2;
	while(k--)
	{
		ReadInt(u1);
		ReadInt(v1);
		ReadInt(u2);
		ReadInt(v2);
		g1[u1].push_back(ii(v1,v2));
		g2[u2].push_back(ii(v1,v2));
	}
	for(int64_t i=1;i<n;i++)
		if(n%i==0)
			Check(i);
	cout<<res;
}

Compilation message (stderr)

chessboard.cpp: In function 'void Check(int64_t)':
chessboard.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int64_t j=0;j<g1[i].size();j++)
                   ~^~~~~~~~~~~~~
chessboard.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int64_t 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: 0 / 23
• Subtask 6: 0 / 30