oj.uz

Submission #167814

# Submission time Handle Problem Language Result Execution time Memory
167814 2019-12-10T09:27:58 Z abil Chessboard (IZhO18_chessboard) C++14
16 / 100
 54 ms 3192 KB 
#include <bits/stdc++.h>

#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define all(s) s.begin(),s.end()
#define int long long

using namespace std;

const int N = (1e5 + 12);
const int mod = (1e9 + 7);
const int INF = (0x3f3f3f3f);

int ans = 1e18;
int n, k, x[2][N], y[2][N];

int get(int x1, int y1, int x2, int y2, int div,int f){
	int blx = (x1 + div - 1) / div, blx2 = (x2 + div - 1) / div;
	int bly = (y1 + div - 1) / div, bly2 = (y2 + div - 1) / div;
	int res = 0ll, odd, even;
	if(blx == blx2){
		int val = x2 - x1 + 1;
		if(bly != bly2){
			int end = (bly + 1) * div - 1;
			val = val * (end - y1 + 1);
			bly++;
			if(bly2 > bly){
				int dif = bly2 - bly + 1;
				val += dif / 2 * div;
			}
			int p = (x2 - x1 + 1) * (y2 - y1 + 1);
			p = p - val;
			if(((bly - 1) + blx) % 2 == f){
				res += val;
			}
			else{
				res += p;
			}			
		}
		else{
			int p = (x2 - x1 + 1) * (y2 - y1 + 1);
			if((bly + blx) % 2 == f){
				res += p;
			}
		}
	}
	else{
		int end = (blx + 1) * div - 1;
		int odd = end - x1 + 1;
		blx++;
		if(blx2 > blx){
			int dif = blx2 - blx + 1;
			odd += dif / 2 * div;
		}
		if(bly != bly2){
			end = (bly + 1) * div - 1;
			int val = end - y1 + 1;
			val = val * odd;
			bly++;
			if(bly2 > bly){
				int dif = bly2 - bly + 1;
				val += dif / 2 * div;
			}
			int p = (x2 - x1 + 1) * (y2 - y1 + 1);
			p = p - val;
			if((bly + blx) % 2 == f){
				res += val;
			}
			else{
				res += p;
			}
		}
		else{
			int p = (y2 - y1 + 1) * odd;
			if(((blx - 1) + bly) % 2 == f){
				res += p;
			}
		}
	}
	return res;
}


void calc(int div){
	int bl = n / div, cnt = 0, x1, y1, cnt1 = 0, x2, y2;
	if(bl & 1){
		cnt += div * div * ((bl + 1) / 2) * ((bl + 1) / 2);
		cnt += div * div * (bl / 2) * (bl / 2);
		cnt1 = n * n - cnt;
		for(int i = 1;i <= k; i++){
			x1 = x[0][i];
			y1 = y[0][i];
			x2 = x[1][i];
			y2 = y[1][i];
			cnt -= get(x1, y1, x2, y2, 1ll, 0ll);
			cnt += get(x1, y1, x2, y2, 1ll, 1ll);
			cnt1 += get(x1, y1, x2, y2, 1ll, 0ll);
			cnt1 -= get(x1, y1, x2, y2, 1ll, 1ll);
		}
		ans = min(ans, cnt);
		ans = min(ans, cnt1);
	}
	else{
		cnt += div * div * (bl / 2) * bl;
		cnt1 = n * n - cnt;
		for(int i = 1;i <= k; i++){
			x1 = x[0][i];
			y1 = y[0][i];
			x2 = x[1][i];
			y2 = y[1][i];
			cnt -= get(x1, y1, x2, y2, 1ll, 0ll);
			cnt += get(x1, y1, x2, y2, 1ll, 1ll);
			cnt1 += get(x1, y1, x2, y2, 1ll, 0ll);
			cnt1 -= get(x1, y1, x2, y2, 1ll, 1ll);
		}
		ans = min(ans, cnt);
		ans = min(ans, cnt1);
	}
}
main()
{
	cin >> n >> k;
	for(int i = 1;i <= k; i++){
		scanf("%lld%lld%lld%lld", &x[0][i], &y[0][i], &x[1][i], &y[1][i]);
	}
	if(n % 2 == 1){
		int x1, y1, x2, y2;
		int cnt = n * n / 2ll + 1ll, cnt1 = n * n / 2ll;
		for(int i = 1;i <= k; i++){
			x1 = x[0][i];
			y1 = y[0][i];
			x2 = x[1][i];
			y2 = y[1][i];
			cnt -= get(x1, y1, x2, y2, 1ll, 0ll);
			cnt += get(x1, y1, x2, y2, 1ll, 1ll);
			cnt1 += get(x1, y1, x2, y2, 1ll, 0ll);
			cnt1 -= get(x1, y1, x2, y2, 1ll, 1ll);
		}
		ans = min(ans, cnt);
		ans = min(ans, cnt1);
	}
	else{
		int x1, y1,x2, y2;
		int cnt = n * n / 2ll, cnt1 = n * n / 2ll;
		for(int i = 1;i <= k; i++){
			x1 = x[0][i];
			y1 = y[0][i];
			x2 = x[1][i];
			y2 = y[1][i];
			cnt -= get(x1, y1, x2, y2, 1ll, 0ll);
			cnt += get(x1, y1, x2, y2, 1ll, 1ll);
			cnt1 += get(x1, y1, x2, y2, 1ll, 0ll);
			cnt1 -= get(x1, y1, x2, y2, 1ll, 1ll);
		}
		ans = min(ans, cnt);
		ans = min(ans, cnt1);
	}
	for(int i = 2;i * i <= n; i++){
		if(n % i == 0){
			calc(i);
			calc(n / i);
		}
	}
	cout << ans;
}
/*
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 get(long long int, long long int, long long int, long long int, long long int, long long int)':
chessboard.cpp:22:17: warning: unused variable 'odd' [-Wunused-variable]
  int res = 0ll, odd, even;
                 ^~~
chessboard.cpp:22:22: warning: unused variable 'even' [-Wunused-variable]
  int res = 0ll, odd, even;
                      ^~~~
chessboard.cpp: At global scope:
chessboard.cpp:122:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
chessboard.cpp: In function 'int main()':
chessboard.cpp:126:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld%lld", &x[0][i], &y[0][i], &x[1][i], &y[1][i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2296 KB Output is correct
2 Correct 12 ms 888 KB Output is correct
3 Correct 25 ms 1528 KB Output is correct
4 Correct 27 ms 1788 KB Output is correct
5 Correct 33 ms 2168 KB Output is correct
6 Correct 22 ms 1404 KB Output is correct
7 Correct 7 ms 504 KB Output is correct
8 Correct 23 ms 1400 KB Output is correct
9 Correct 54 ms 3192 KB Output is correct
10 Correct 31 ms 1916 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 16.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2296 KB Output is correct
2 Correct 12 ms 888 KB Output is correct
3 Correct 25 ms 1528 KB Output is correct
4 Correct 27 ms 1788 KB Output is correct
5 Correct 33 ms 2168 KB Output is correct
6 Correct 22 ms 1404 KB Output is correct
7 Correct 7 ms 504 KB Output is correct
8 Correct 23 ms 1400 KB Output is correct
9 Correct 54 ms 3192 KB Output is correct
10 Correct 31 ms 1916 KB Output is correct
11 Incorrect 2 ms 376 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 38 ms 2296 KB Output is correct
10 Correct 12 ms 888 KB Output is correct
11 Correct 25 ms 1528 KB Output is correct
12 Correct 27 ms 1788 KB Output is correct
13 Correct 33 ms 2168 KB Output is correct
14 Correct 22 ms 1404 KB Output is correct
15 Correct 7 ms 504 KB Output is correct
16 Correct 23 ms 1400 KB Output is correct
17 Correct 54 ms 3192 KB Output is correct
18 Correct 31 ms 1916 KB Output is correct
19 Incorrect 2 ms 376 KB Output isn't correct
20 Halted 0 ms 0 KB -