oj.uz

Submission #385446

# Submission time Handle Problem Language Result Execution time Memory
385446 2021-04-04T09:51:56 Z vanic Chessboard (IZhO18_chessboard) C++14
8 / 100
 42 ms 3820 KB 
#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){
			br+=dodaj((x2-x1+1)*(y2-y1+1), pocx+pocy, p);
		}
		else if(pocx==krajx){
			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, pocx*val);
			cor2=max(y1, pocy*val);
			cor3=x2;
			cor4=y2;
			br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), pocx+pocy, p);
			
			pocy++;
			krajy--;
			if(pocy>krajy){
				continue;
			}
			cor1=x1;
			cor2=pocy*val;
			cor3=x2;
			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;
			}
		}
		else if(pocy==krajy){
			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, pocx*val);
			cor2=max(y1, pocy*val);
			cor3=x2;
			cor4=y2;
			br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), pocx+pocy, 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{
			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, pocx*val);
			cor2=max(y1, pocy*val);
			cor3=x2;
			cor4=y2;
			br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), pocx+pocy, p);

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

			cor1=max(x1, pocx*val);
			cor2=y1;
			cor3=x2;
			cor4=min(y2, (pocy+1)*val-1);
			br+=dodaj((cor3-cor1+1)*(cor4-cor2+1), pocx+pocy, p);
			
			pocx++;
			krajx--;
			if(krajx>=pocx){
				cor1=pocx*val;
				cor2=y1;
				cor3=(pocx+1)*val-1;
				cor4=(pocy+1)*val-1;
				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;
				}
				
				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++;
			
			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;
			}
		}
	}
	return br;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	ll uk;
	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)*(d-b);
		l[i]={a, b, c, d};
	}
	ll sol=1e18;
	ll br1, br2;
	ll crno, bijelo;
	for(ll i=1; i*i<=n; i++){
//		cout << 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;
			assert(crno+bijelo==n*n);
			sol=min(sol, crno-br1+k-br1);
			swap(crno, bijelo);
			sol=min(sol, crno-br2+k-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+k-br1);
				swap(crno, bijelo);
				sol=min(sol, crno-br2+k-br2);
			}
		}
	}
	cout << sol << '\n';
	return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2724 KB Output is correct
2 Correct 8 ms 1004 KB Output is correct
3 Correct 18 ms 1920 KB Output is correct
4 Correct 23 ms 1900 KB Output is correct
5 Correct 24 ms 2540 KB Output is correct
6 Correct 16 ms 1772 KB Output is correct
7 Correct 4 ms 620 KB Output is correct
8 Correct 16 ms 1772 KB Output is correct
9 Correct 42 ms 3820 KB Output is correct
10 Correct 22 ms 2284 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2724 KB Output is correct
2 Correct 8 ms 1004 KB Output is correct
3 Correct 18 ms 1920 KB Output is correct
4 Correct 23 ms 1900 KB Output is correct
5 Correct 24 ms 2540 KB Output is correct
6 Correct 16 ms 1772 KB Output is correct
7 Correct 4 ms 620 KB Output is correct
8 Correct 16 ms 1772 KB Output is correct
9 Correct 42 ms 3820 KB Output is correct
10 Correct 22 ms 2284 KB Output is correct
11 Incorrect 1 ms 492 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -