oj.uz

Submission #377601

# Submission time Handle Problem Language Result Execution time Memory
377601 2021-03-14T11:11:22 Z SeDunion Chessboard (IZhO18_chessboard) C++17
8 / 100
 40 ms 3820 KB 
#include<bits/stdc++.h>
#ifndef LOCAL
#define cerr if(false)cerr
#endif // LOCAL
using namespace std;
using ll = long long;
const int N = 1e6 + 66;

#define y1 slkdjflkjsdlfkjlskjfjklkdjslfjslkdjflkjlsdkjflkjslkdjflkdslfkjsldklkjsdjfntnfj
#define y0 alsjdljrktnmndfdfgjhkjhdkfjgbtnmbmfhkjgdkjfhkjxhkjhgtgbhhdjbhjhtdbjbhjhtbhbgbb

int x0[N], y0[N], x1[N], y1[N], n, k;

ll cnt(int d, int x, int y) {
	if (x < 0 || y < 0) return 0;
	int X = x / d, Y = y / d;
	if (0) {
		ll cur = 0;
		for (int i = 0 ; i < X * d ; ++ i) {
			for (int j = 0 ; j < Y * d ; ++ j) {
				if ((i / d + j / d) % 2 == 0) cur++;
			}
		}
		return cur;
	}
	cerr << d << " : " << x << " " << y << " " << X << " " << Y << endl;
	ll cur = ((X * 1ll * Y + 1) / 2) * d;
	ll Xc = Y % 2 == 1 ? X / 2 : (X + 1) / 2;
	ll Yc = X % 2 == 1 ? Y / 2 : (Y + 1) / 2;
	cur += Xc * d * (y - Y * d + 1);
	cur += Yc * d * (x - X * d + 1);
	if ((X + Y) % 2 == 0)
		cur += (x - X * d + 1) * 1ll * (y - Y * d + 1);
	return cur;
}

ll solve(int d) {
	ll cur = cnt(d, n-1, n-1);
	for (int i = 0 ; i < k ; ++ i) {
		ll black = cnt(d, x1[i], y1[i]) - cnt(d, x0[i] - 1, y1[i]) - cnt(d, x1[i], y0[i] - 1) + cnt(d, x0[i] - 1, y0[i] - 1);
		ll area = (y1[i] - y0[i] + 1) * 1ll * (x1[i] - x0[i] + 1);
		//cerr << d << " " << black << " " << area << " d/black/area\n";
		cur += area - black * 2;
	}
	return cur;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> k;
	for (int i = 0 ; i < k ; ++ i) {
		cin >> x0[i] >> y0[i] >> x1[i] >> y1[i];
		x0[i]--, y0[i]--, x1[i]--, y1[i]--;
	}
	ll ans = n * 1ll * n;
	for (int d = 1 ; d < n ; ++ d) {
		if (n % d == 0) {
			for (int i = 0 ; i < n ; ++ i) {
				for (int j = 0 ; j < n ; ++ j) {
					if ((i / d + j / d) % 2 == 0) cerr << "X";
					else cerr << ".";
				}
				cerr << "\n";
			}
			cerr << "\n";
			ll cur = solve(d);
			ans = min(ans, min(cur, n * 1ll * n - cur));
		}
	}
	cout << ans;
}

Compilation message

chessboard.cpp: In function 'int main()':
chessboard.cpp:61:9: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   61 |      if ((i / d + j / d) % 2 == 0) cerr << "X";
      |         ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 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 31 ms 1388 KB Output is correct
2 Correct 8 ms 1004 KB Output is correct
3 Correct 18 ms 1900 KB Output is correct
4 Correct 20 ms 1900 KB Output is correct
5 Correct 25 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 40 ms 3820 KB Output is correct
10 Correct 23 ms 2284 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 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 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1388 KB Output is correct
2 Correct 8 ms 1004 KB Output is correct
3 Correct 18 ms 1900 KB Output is correct
4 Correct 20 ms 1900 KB Output is correct
5 Correct 25 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 40 ms 3820 KB Output is correct
10 Correct 23 ms 2284 KB Output is correct
11 Incorrect 1 ms 364 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 364 KB Output isn't correct
3 Halted 0 ms 0 KB -