Submission #378569

#	Time	Username	Problem	Language	Result	Execution time	Memory
378569		ElaineHuang	Chessboard (IZhO18_chessboard)	C++14	70 / 100	270 ms	2924 KiB

chessboard

#include<bits/stdc++.h>
#define debug 0
#define int long long
#define min trash
using namespace std;
int b[100005][2];//black squares
//vector<int> factor;
int factor[100005],fs;//factor size
int N;
int Min(int a,int b)
{
	return a<b?a:b;
}
int p(int f)
{
	int o=((N/f)*(N/f)/2)*f*f;//o->odd blocks
	int e=N*N-o;//e->even blocks
	if(debug) printf("f%lld o%lld e%lld\n",f,o,e);//
	return Min(b[f][1]+e-b[f][0],b[f][0]+o-b[f][1]);//e黑//o黑 
}
signed main()
{
	int K,x1,x2,y1,y2;
	scanf("%lld %lld",&N,&K);
	int g=(int)sqrt(N);
	//factor.clear();
	memset(b,0,sizeof(b));
	for(int i=1;i<=g;i++)
	{
		if(!(N%i))
		{
			factor[fs]=i;
			fs++;
		}
		if(debug) printf("i=%lld\n",i);//
	}
	if(debug) printf("%lld, g%lld\n",fs,g);//
	while(K--)
	{
		scanf("%lld %lld %lld %lld",&x1,&y1,&x2,&y2);
		x1--,y1--,x2--,y2--;
		for(int i=0;i<fs;i++)
		{
			int a;//determine 0 or 1
			int f;//factor
			f=factor[i];
			a=x1/f+y1/f;
			a%=2;
			b[f][a]++;
			
			if(f==N/f) break;
			if(f==1) continue;
			
			f=N/factor[i];
			a=x1/f+y1/f;
			a%=2;
			b[f][a]++;
		}
	}
	int ans=N*N;
	for(int i=0;i<fs;i++)
	{
		int f;
		f=factor[i];//p->paint幾格 
		ans=Min(p(f),ans);
		if(f==N/f) break;
		if(f==1) continue;
		f=N/f;
		ans=Min(p(f),ans);
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'int main()':
chessboard.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |  scanf("%lld %lld",&N,&K);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
chessboard.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |   scanf("%lld %lld %lld %lld",&x1,&y1,&x2,&y2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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