Submission #334389

#	Time	Username	Problem	Language	Result	Execution time	Memory
334389		tengiz05	Chessboard (IZhO18_chessboard)	C++17	39 / 100	94 ms	2664 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
const int mod = 1e9+7, N = 2e5+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val);}
int a[N], n, m, k;

void solve(int test_case){
	int i, j;
	cin >> n >> k;
	vector<pii> v;
	for(i=0;i<k;i++){
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		v.pb({x1, y1});
	}
	int ans = mod;
	
	for(int s=1; (int)s*s<=n; s++){
		if(n%s == 0){
			{
				int tmp = (int)s*s;
				int sum = ((int)(n*n/tmp)/2ll)*tmp;
				int sz = (s);
				int ans1=sum;
				for(i=0;i<k;i++){
					auto [x, y] = v[i];
					x+=sz-1, y+=sz-1;
					x/=sz, y/=sz;
					if((x+y)%2 == 0){
						ans1++;
					}else ans1--;
				}
				ans = min(ans, ans1);
			//	cout << ans << ' ';
				if((n*n/tmp)%2!=0)sum += tmp;
				ans1 = sum;
				
				for(i=0;i<k;i++){
					auto [x, y] = v[i];
					x+=sz-1, y+=sz-1;
					x/=sz, y/=sz;
					if((x+y)%2 == 1){
						ans1++;
					}else ans1--;
				}
				ans = min(ans, ans1);
			//	cout << ans << ' ';
			}
			if((int)s*s != n && s != 1){
				int sz = (n/s);
				int tmp = (int)(sz)*(sz);
				int sum = ((int)(n*n/tmp)/2ll)*tmp;
				int ans1=sum;
				for(i=0;i<k;i++){
					auto [x, y] = v[i];
					x+=sz-1, y+=sz-1;
					x/=sz, y/=sz;
					if((x+y)%2 == 0){
						ans1++;
					}else ans1--;
				}
				ans = min(ans, ans1);
			//	cout << ans << ' ';
				if((int)(n*n/tmp)%2ll!=0)sum += tmp;
				ans1 = sum;
				
				for(i=0;i<k;i++){
					auto [x, y] = v[i];
					x+=sz-1, y+=sz-1;
					x/=sz, y/=sz;
					if((x+y)%2 == 1){
						ans1++;
					}else ans1--;
				}
				ans = min(ans, ans1);
			//	cout << ans << ' ';
			}
		}
	}
	cout << ans << '\n';
	return;
}
/*

4 4
4 1 4 1
4 2 4 2
4 3 4 3
4 4 4 4


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

5 4
1 2 1 2
1 3 1 3
1 4 1 4
2 2 2 2

3 9
1 1 1 1
2 2 2 2
3 3 3 3
1 2 1 2
1 3 1 3
2 1 2 1
3 1 3 1
3 2 3 2
2 3 2 3


*/
signed main(){
	FASTIO;
#define MULTITEST 0
#if MULTITEST
	int ___T;
	cin >> ___T;
	for(int T_CASE = 1; T_CASE <= ___T; T_CASE++)
		solve(T_CASE);
#else
	solve(1);
#endif
	return 0;
}

Compilation message (stderr)

chessboard.cpp: In function 'void solve(long long int)':
chessboard.cpp:17:9: warning: unused variable 'j' [-Wunused-variable]
   17 |  int i, j;
      |         ^

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