Submission #171648

#	Time	Username	Problem	Language	Result	Execution time	Memory
171648		Lightning	Chessboard (IZhO18_chessboard)	C++14	39 / 100	179 ms	9720 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 int ll

const int N = 2000;
const int INF = 2e9 + 5;

int sc[N][N];

void solve1(int n, int k) {
	for(int it = 1; it <= k; ++it) { 
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		//swap(x1, y1);
		//swap(x2, y2);
		for(int i = x1; i <= x2; ++i) {
			++sc[i][y1];
		}
		for(int i = x1; i <= x2; ++i) {
			--sc[i][y2 + 1];
		}
	}
	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 res1 = 0, res2 = 0;
		for(int i = 1; i <= n; ++i) {
			int cur = 0;
			bool vs = ((((i - 1) / di) & 1) ^ 1);
			for(int j = 1; j <= n; ++j) {
				cur += sc[i][j];
				// (cur > 0) -> black : white
				if(cur > 0) {
					if((((j - 1) / di) & 1) ^ vs) ++res1;
					else ++ res2;	
				} else {
					if((((j - 1) / di) & 1) ^ vs) ++res2;
					else ++res1;
				}
			}
		}
		/*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) cout << 1;
				else cout << 2;	
			}
			cout << '\n';
		}
		cout << '\n';*/
		ans = min(ans, min(res1, res2));
	}
	cout << ans;
}

/*void solve2(int n, int k) {
	
}*/

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

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