제출 #502494

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
502494		Mr_Husanboy	Chessboard (IZhO18_chessboard)	C++14	70 / 100	230 ms	2596 KiB

chessboard

// Muallif: Mansuraliyev Husanboy Murotali o'g'li  >> NamPS

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const double PI=3.1415926535897932384626433832795;
// 0-9 >> 48-57;    A-Z>>65-90   and   a-z>>97-122 respectively;


int main(){
	ios;
	ll n,q; cin>>n>>q;
	vector<ll> a;
	a.push_back(1ll);
	ll b=sqrt(n);
	for(ll i=2;i<sqrt(n);i++){
		if(n%i==0){
			a.push_back(i); a.push_back(n/i);
		}
	}
	if(b*b==n){
		a.push_back(b);
	}
	vector<ll> ans,ans2;
	ll sz=a.size();
	for(auto u:a){
		ll x=n/u;
		if(x%2ll==0){
			ans.push_back((n*n)/2ll);
			ans2.push_back((n*n)/2ll);
		}else{
			ll k=(n*n-u*u)/2ll+u*u;
			ans.push_back(k);
			ans2.push_back(n*n-k);
		}
	}
	while(q--){
		ll x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		for(int i=0;i<sz;i++){
			ll u=a[i];
			/*ll x=n/u;
			ll black=0ll,white=0ll;
			ll tx2=x2-x2%u,tx1=x1-(x1%u==0ll||x1%u==1ll?u:x1%u)+u+(x1%u==1ll||u==1ll?0ll:1ll),ty1=y1-(y1%u==0ll||y1%u==1ll?u:y1%u)+u+(y1%u==1||u==1ll?0ll:1ll),ty2=y2-y2%u;
			//cout<<u<<": "<<tx1<<' '<<ty1<<' '<<tx2<<' '<<ty2<<endl;
			if(tx1<=tx2&&ty1<=ty2){
				
			}else{
				
			}*/
			ll x=(x1+u-1ll)/u,y=(y1+u-1ll)/u;
			//cout<<u<<": "<<x<<' '<<y<<">> ";
			if((x+y)%2==0){
				
				ans[i]--; ans2[i]++;//cout<<ans[i]<<endl;
			}else{
				
				ans[i]++; ans2[i]--;//cout<<ans[i]<<endl;
			}
		}
	}
	ll mn=1e18;
	for(int i=0;i<sz;i++){
		//cout<<ans[i]<<' '<<ans2[i]<<endl;
		mn=min(mn,min(ans[i],ans2[i]));
	}
	cout<<mn;
}

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