oj.uz

Submission #378576

# Submission time Handle Problem Language Result Execution time Memory
378576 2021-03-17T01:55:27 Z 8e7 Chessboard (IZhO18_chessboard) C++14
8 / 100
 25 ms 1516 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
struct rect{
	int x1, y1, x2, y2;
	rect() {
		x1 = 0, y1 = 0, x2 = 0, y2 = 0;
	}
	rect(int a, int b, int c, int d) {
		x1 = a, y1 = b, x2 = c, y2 = d;
	}
};
vector<rect> v;

inline ll wnum(ll x, ll y, ll len) {
	ll ret = 0;
	ll cx = x / len, cy = y / len;
	if (cx % 2 == 0 || cy % 2 == 0) {
		ret += len * len * (cx * cy / 2);
	} else {
		ret += len * len * ((cx * cy + 1) / 2);
	}
	if (cy % 2 == 0) { //white
		ret += y % len * ((cx + 1) / 2);
	} else {
		ret += y % len * (cx / 2);
	}
	if (cx % 2 == 0) {
		ret += x % len * ((cy + 1) / 2);
	} else {
		ret += x % len * (cy / 2);
	}
	if ((cx + cy % 2) == 0) ret += (cx % len) * (cy % len);
	return ret;
}
ll solve(ll n, ll len) {
	ll val = wnum(n, n, len), block = n / len;
	for (rect a:v) {
		val += (a.x1 / len + a.y1 / len) % 2 ? -1 : 1;
	}
	val = min(val, n * n - val);
	//cout << len << " " << val << endl;
	return val;
}
int main() {
	io
	ll n, k;
	cin >> n >> k;
	for (int i = 0;i < k;i++) {
		ll x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		x1--, y1--, x2--, y2--;
		v.push_back(rect(x1, y1, x2, y2));
	}
	ll ans = 1LL<<60;
	for (ll i = 1;i * i <= n;i++) {
		if (n % i == 0) {
			ans = min(ans, solve(n, i));
			if (i * i != n && i != 1) {
				ans = min(ans, solve(n, n / i));
			}
		}
	}
	cout << ans << endl;
}
/*
2 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
 */

Compilation message

chessboard.cpp: In function 'long long int solve(long long int, long long int)':
chessboard.cpp:46:28: warning: unused variable 'block' [-Wunused-variable]
   46 |  ll val = wnum(n, n, len), block = n / len;
      |                            ^~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct

Subtask #2
0 / 8.0

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

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 Incorrect 25 ms 1516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Incorrect 25 ms 1516 KB Output isn't correct
10 Halted 0 ms 0 KB -