Submission #171663

#	Time	Username	Problem	Language	Result	Execution time	Memory
171663		Lightning	Chessboard (IZhO18_chessboard)	C++14	70 / 100	476 ms	6008 KiB

chessboard

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define show(a) cerr << #a <<" -> "<< a <<"\n"
#define fo(a, b, c, d) for(int (a) = (b); (a) <= (c); (a) += (d))
#define foo(a, b, c ,d) for(int (a) = (b); (a) >= (c); (a) -= (d))
#define y1 GG
#define int ll

const int N = 1e5 + 5;
const ll INF = 1e12 + 5;

//int sc[N][N];
int x1[N], x2[N], y1[N], y2[N];

void solve1(int n, int k) {
	for(int it = 1; it <= k; ++it) { 
		//int x1, y1, x2, y2;
		cin >> x1[it] >> y1[it] >> x2[it] >> y2[it];
		//cin >> x1 >> y1 >> x2 >> y2;
	}
	vector <int> d;
	d.pb(1);
	for(int i = 2; i * i <= n; ++i) {
		if(n % i == 0) {
			d.pb(i);
			if(i != n / i) d.pb(n / i);
		}
	}
	int ans = INF;
	for(int di : d) {
		/*int black = 0;
		for(int i = 1; i <= n; ++i) {
			bool vs = ((((i - 1) / di) & 1) ^ 1);
			for(int j = 1; j <= n; ++j) {
				if((((j - 1) / di) & 1) ^ vs) ++black;//cout << 1;
				//else cout << 2;	
			}
			//cout << '\n';
		}
		cout << '\n';
		if((row1 * cntrow1 + row2 * cntrow2) * di * di != black) {
			show(di);
			show(row1);
			show(cntrow1);
			show(row2);
			show(cntrow2);
			show(black);
		}*/
		int row1 = (n / di + 1) / 2, row2 = (n / di) / 2;
		int res1 = (row1 * row1 + row2 * row2) * di * di, res2 = n * n - res1;
		for(int it = 1; it <= k; ++it) {
			int i = x1[it], j = y1[it];
			bool vs = ((((i - 1) / di) & 1) ^ 1);
			if((((j - 1) / di) & 1) ^ vs) {++res2; --res1;}
			else {++res1; --res2;}
		}
		ans = min(ans, min(res1, res2));
	}
	cout << ans;
}

main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, k;
	cin >> n >> k;
	//if(n <= 1000) {
		solve1(n, k);
	//} else {
	//	solve2(n, k);
	//}
	return 0;
}
/*
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

	If you only do what you can do, 
	You will never be more than you are now!	
*/

Compilation message (stderr)

chessboard.cpp:83:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

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