Submission #385451

#	Time	Username	Problem	Language	Result	Execution time	Memory
385451		vanic	Chessboard (IZhO18_chessboard)	C++14	100 / 100	811 ms	4460 KiB

chessboard

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#include <stack>
#include <map>
#include <queue>
#include <vector>
#include <cstring>
#include <array>
#include <bitset>
#include <cassert>

using namespace std;

typedef long long ll;

const int maxn=1e5+5;

array < int, 4 > l[maxn];
ll n, k;

inline ll dodaj(ll val, int br, bool p){
	if((br&1 && p) || (!(br&1) && !p)){
		return val;
	}
	return 0;
}
bool stima(int br, bool p){
	return (br&1 && p) || (!(br&1) && !p);
}

ll probaj(ll val, bool p){
	ll br=0;
	ll x1, y1, x2, y2;
	ll pocx, pocy, krajx, krajy;
	ll cor1, cor2, cor3, cor4;
	for(int i=0; i<k; i++){
		x1=l[i][0];
		y1=l[i][1];
		x2=l[i][2];
		y2=l[i][3];
		pocx=x1/val;
		pocy=y1/val;
		krajx=x2/val;
		krajy=y2/val;
		if(pocx==krajx && pocy==krajy){
//			cout << "izi!" << endl;
			br+=dodaj((x2-x1+1)*(y2-y1+1), pocx+pocy, p);
		}
		else if(pocx==krajx){
//			cout << "tu sam!" << endl;
			cor1=x1;
			cor2=y1;
			cor3=min(x2, (pocx+1)*val-1);
			cor4=min(y2, (pocy+1)*val-1);
//			cout << cor1 << ' ' << cor2 << ' ' << cor3 << ' ' << cor4 << endl;
			br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), pocx+pocy, p);
			
			cor1=max(x1, krajx*val);//
			cor2=max(y1, krajy*val);//fixaj svugdje! bilo je poc
			cor3=x2;
			cor4=y2;
//			cout << cor1 << ' ' << cor2 << ' ' << cor3 << ' ' << cor4 << endl;
			br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), krajx+krajy, p); //fixaj i ovo
			
			pocy++;
			krajy--;
			if(pocy>krajy){
				continue;
			}
			cor1=x1;
			cor2=pocy*val;
			cor3=x2;
			cor4=(pocy+1)*val-1;
			
//			cout << cor1 << ' ' << cor2 << ' ' << cor3 << ' ' << cor4 << endl;
//			cout << pocy << ' ' << krajy << endl;
			if(stima(pocx+pocy, p)){
				br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajy-pocy+2)/2);
			}
			else{
				br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajy-pocy+1)/2);
			}
		}
		else if(pocy==krajy){
//			cout << "ovdje!" << endl;
			cor1=x1;
			cor2=y1;
			cor3=min(x2, (pocx+1)*val-1);
			cor4=min(y2, (pocy+1)*val-1);
			br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), pocx+pocy, p);
			
			cor1=max(x1, krajx*val);
			cor2=max(y1, krajy*val);
			cor3=x2;
			cor4=y2;
			br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), krajx+krajy, p);
			
			pocx++;
			krajx--;
			if(pocx>krajx){
				continue;
			}
			cor1=pocx*val;
			cor2=y1;
			cor3=(pocx+1)*val-1;
			cor4=y2;
			
			if(stima(pocx+pocy, p)){
				br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajx-pocx+2)/2);
			}
			else{
				br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajx-pocx+1)/2);
			}
		}
		else{
//			cout << "kunito!" << endl;

			cor1=x1;
			cor2=y1;
			cor3=min(x2, (pocx+1)*val-1);
			cor4=min(y2, (pocy+1)*val-1);
			br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), pocx+pocy, p);

			cor1=max(x1, krajx*val);
			cor2=max(y1, krajy*val);
			cor3=x2;
			cor4=y2;
			br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), krajx+krajy, p);

			cor1=x1;
			cor2=max(y1, krajy*val);
			cor3=min(x2, (pocx+1)*val-1);
			cor4=y2;
			br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), pocx+krajy, p);

			cor1=max(x1, krajx*val);
			cor2=y1;
			cor3=x2;
			cor4=min(y2, (pocy+1)*val-1);
			br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), krajx+pocy, p);
//			cout << br <<  endl;
			pocx++;
			krajx--;
			if(krajx>=pocx){
				cor1=pocx*val;
				cor2=y1;
				cor3=(pocx+1)*val-1;
				cor4=(pocy+1)*val-1;
//				cout << cor1 << ' ' << cor2 << ' ' << cor3 << ' '<< cor4 << endl;
//				cout << pocx << ' ' << pocy << endl;
				if(stima(pocx+pocy, p)){
					br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajx-pocx+2)/2);
				}
				else{
//					cout << "uso" << endl;
					br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajx-pocx+1)/2);
//					cout << br << endl;
				}
				
				cor2=krajy*val;
				cor4=y2;
				if(stima(pocx+krajy, p)){
					br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajx-pocx+2)/2);
				}
				else{
					br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajx-pocx+1)/2);
				}
			}
			pocx--;
			krajx++;
			
			pocy++;
			krajy--;
			if(krajy>=pocy){
				cor1=x1;
				cor2=pocy*val;
				cor3=(pocx+1)*val-1;
				cor4=(pocy+1)*val-1;
				if(stima(pocx+pocy, p)){
					br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajy-pocy+2)/2);
				}
				else{
					br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajy-pocy+1)/2);
				}
				
				cor1=krajx*val;
				cor3=x2;
				if(stima(krajx+pocy, p)){
					br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajy-pocy+2)/2);
				}
				else{
					br+=(cor3-cor1+1)*(cor4-cor2+1)*((krajy-pocy+1)/2);
				}
			}
			pocy--;
			krajy++;
//			cout << br << endl;
			if(((pocx+pocy)&1 && p) || (!((pocx+pocy)&1) && !p)){
				br+=((krajx-pocx-1)*(krajy-pocy-1)+1)/2*val*val;
			}
			else{
				br+=(krajx-pocx-1)*(krajy-pocy-1)/2*val*val;
			}
		}
	}
//	cout << br << endl;
	return br;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	ll uk=0;
	int a, b, c, d;
//	cout << "proso" << endl;
	for(int i=0; i<k; i++){
//		cout << "uso" << endl;
		cin >> a >> b >> c >> d;
		a--;
		b--;
		c--;
		d--;
		uk+=(ll)(c-a+1)*(d-b+1);
		l[i]={a, b, c, d};
	}
	ll sol=1e18;
	ll br1, br2;
	ll crno, bijelo;
	for(ll i=1; i*i<=n; i++){
//		cout << "na " << i << endl;
		if(n%i==0){
			br1=probaj(i, 0);
			br2=probaj(i, 1);
			crno=((n/i)*(n/i)+1)/2*i*i;
			bijelo=(n/i)*(n/i)/2*i*i;
//			cout << "boje " << bijelo << ' ' << crno << endl;
//			cout << "brojevi " << br1 << ' ' << br2 << endl;
			sol=min(sol, crno-br1+uk-br1);
			swap(crno, bijelo);
			sol=min(sol, crno-br2+uk-br2);
			if(i!=1 && i*i!=n){
				br1=probaj(n/i, 0);
				br2=probaj(n/i, 1);
				crno=(i*i+1)/2*(n/i)*(n/i);
				bijelo=i*i/2*(n/i)*(n/i);
				sol=min(sol, crno-br1+uk-br1);
				swap(crno, bijelo);
				sol=min(sol, crno-br2+uk-br2);
			}
		}
	}
	cout << sol << '\n';
	return 0;
}

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