Submission #378552

#	Time	Username	Problem	Language	Result	Execution time	Memory
378552		Seanliu	Chessboard (IZhO18_chessboard)	C++14	70 / 100	1279 ms	5996 KiB

chessboard

#include <iostream>
#define int long long int
#define ericxiao ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

const int maxN = 1e5 + 326;

struct Rect{
	int l, r, d, u, A;
	Rect(){}
	Rect(int l, int r, int d, int u): l(l), r(r), d(d), u(u){
		A = (r - l + 1) * (u - d + 1);
	}
} rects[maxN];

inline bool onDiag(int x, int y, int d){
	return	(((x % (2 * d)) < d) == ((y % (2 * d)) < d)); 
}

inline int id(int x, int y, int d){
	return x / d * maxN + y / d;		
}

int N, K;

inline int check(int d){
	//top left is black
	//cout << "d = " << d << endl;
	int _ans = maxN * maxN, tmp = ((N / d) * (N / d) + 1) / 2 * (d * d);
	//cout << "1tmp = " << tmp << endl;
	for(int i = 0; i < K; i++){
		if(id(rects[i].l, rects[i].u, d) == id(rects[i].r, rects[i].d, d)){
			//cout << onDiag(rects[i].l, rects[i].u, d) && onDiag(rects[i].r, rects[i].d, d);
			if(onDiag(rects[i].l, rects[i].u, d) && onDiag(rects[i].r, rects[i].d, d)) tmp -= rects[i].A;
			else tmp += rects[i].A;
		} else {
			tmp = maxN * maxN;
			break;
		}
	}
	cout << endl;
	//cout << "1: " << tmp << endl;
	_ans = min(_ans, tmp);
	tmp = ((N / d) * (N / d)) / 2 * (d * d);
	for(int i = 0; i < K; i++){
		if(id(rects[i].l, rects[i].u, d) == id(rects[i].r, rects[i].d, d)){
			if(onDiag(rects[i].l, rects[i].u, d) && onDiag(rects[i].r, rects[i].d, d)) tmp += rects[i].A;
			else tmp -= rects[i].A;
		} else {
			tmp = maxN * maxN;
			break;
		}	
	}
	//cout << "2: " << tmp << endl;
	_ans = min(_ans, tmp);
	//cout << "d = " << d << ", ans = " << _ans << endl;
	return _ans;
	//top right is black
}

signed main(){
	ericxiao;
	cin >> N >> K;
	int l, r, d, u;
	for(int i = 0; i < K; i++){
		cin >> l >> d >> r >> u;
		l--; d--; r--; u--;
		rects[i] = Rect(l, r, d, u);
		//cout << "rects[i] a = " << rects[i].A << endl;
	}
	int ans = maxN * maxN;
	for(int div = 1; div * div <= N; div++){
		if(!(N % div)){
			ans = min(ans, check(div));
			if(div != 1) ans = min(ans, check(N / div));
		}
	}
	cout << ans << endl;
}

/*
 * 
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
*/

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