제출 #342183

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
342183		David_M	Chessboard (IZhO18_chessboard)	C++14	100 / 100	839 ms	6808 KiB

chessboard

#include <bits/stdc++.h> 
#define ll long long
#define pb push_back
#define F first
#define S second
using namespace std;
const ll N=1000006, INF=1e18;
ll e, t, n, m, a[N], i, j, k, u, x1, x2, X1, X2, ans[N], xl[N], yl[N], xr[N], yr[N], Ans, sz, w, r, X, Y, xx, yy, xxx, yyy, A, B;
vector <int> v;

ll calc(ll x, ll y){
	if(!x||!y) return 0;
	t=0;
	X=x/e*e;
	Y=y/e*e;
	
	xx=X/e;
	yy=Y/e;
	
	t+=(((xx*yy+1)/2)*e*e);
	xxx=x-X;
	yyy=y-Y;
	
	if(xx&1) B=(yy>>1);
	else B=(yy+1>>1);
	
	if(yy&1) A=(xx>>1);
	else A=(xx+1>>1);
	
	t+=(B*xxx*e);
	t+=(A*yyy*e);
	
	if(!((X/e+Y/e)&1)) t+=(xxx*yyy);
//	cout<<x<<" "<<y<<" "<<t<<endl;
	return t;
}

int main(){ios_base::sync_with_stdio(false), cin.tie(0);
	long long ee;
	cin>>n>>m;
	Ans=INF;
		
	for (int i=1; i<=m; i++)
		cin>>xl[i]>>yl[i]>>xr[i]>>yr[i],
		a[i]=(xr[i]-xl[i]+1)*(yr[i]-yl[i]+1);
		
	
	for (int i=1; i<n; i++)
		if(n%i==0)
			v.pb(i);
	k=v.size();
	
	for(int i=0; i<k; i++){
		e=v[i];
		ans[i]=(n*n/e/e+1)/2*e*e;//cout<<ans[i]<<" ";
		for (int j=1; j<=m; j++)
			ans[i]+=a[j],
			ans[i]-=2*(calc(xr[j], yr[j])-(calc(xl[j]-1, yr[j])+calc(xr[j], yl[j]-1)-calc(xl[j]-1, yl[j]-1)));
		Ans=min(Ans, min(ans[i], n*n-ans[i]));//cout<<ans[i]<<endl;
	}
	cout<<Ans;
	
}
/*
6 8
3 3 3 3
1 2 1 2
3 4 3 4
5 5 5 5
4 3 4 3
4 4 4 4
2 1 2 1
3 6 3 6

4 1
4 1 4 4
*/

컴파일 시 표준 에러 (stderr) 메시지

chessboard.cpp: In function 'long long int calc(long long int, long long int)':
chessboard.cpp:25:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |  else B=(yy+1>>1);
      |          ~~^~
chessboard.cpp:28:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |  else A=(xx+1>>1);
      |          ~~^~
chessboard.cpp: In function 'int main()':
chessboard.cpp:39:12: warning: unused variable 'ee' [-Wunused-variable]
   39 |  long long ee;
      |            ^~

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