Submission #682887

#	Time	Username	Problem	Language	Result	Execution time	Memory
682887		iskhakkutbilim	Chessboard (IZhO18_chessboard)	C++14	47 / 100	93 ms	15152 KiB

chessboard

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 1e5;
vector<int> g[N+1];
int odd[N+1], even[N+1];
int n, k;
int dp[1001][1001];
int isprime(int n){
	for(int i =2; i * i <= n; i++){
		if(n%i==0) return 0;
	}
	return 1;
}


int get(int x, int y, int x1, int y1){
	return dp[x1][y1] - dp[x-1][y1] - dp[x1][y-1]+dp[x-1][y-1];
}



/*
6 8
1 3 1 3
1 4 1 4
2 3 2 3
2 4 2 4
3 1 3 1
3 2 3 2
4 1 4 1
4 2 4 2
*/
main(){
	cin >> n >> k;
	int Pr = isprime(n);
	int x[k], y[k], x1[k], y1[k];
	for(int i = 0;i < k; i++){
		cin >> x[i] >> y[i] >> x1[i] >> y1[i];
		if(Pr==0) dp[x[i]][y[i]] = 1;
		odd[x[i]] += (y[i]%2==1);
		even[x[i]]+= (y[i]%2==0);
	}
	int answer = INT_MAX;
//	if(k == 0){
//		for(int i = 1;i * i < n*n; i++){
//			if(n%i==0){
//				int j = n / i, black = 0;
//				for(int c = 1; c <= j; c++){
//					if(c%2==1){
//						black+= (j / 2) * (i*i);
//					}else{
//						black+= (j-(j / 2))*(i*i);
//					}
//				}
//				answer = min(answer, black);
//			}
//		}
//		cout << answer;
//		return 0;
//	}
	if(Pr){
		int S = 0, S1 = 0;
		for(int i = 1;i <= n; i++){
			if(i%2==1){
				S+= even[i];
				S+= ((n+1)/2) - odd[i];
			}else{
				S+= odd[i];
				S+= (n / 2)-even[i];
			}
		}
		for(int i = 1;i <= n; i++){
			if(i%2==1){
				S1+= odd[i];
				S1+= (n / 2)-even[i];
			}else{
				S1+= even[i];
				S1+= ((n+1)/2) - odd[i];
			}
		}
		cout << min(S, S1);
		return 0;
	}
//	cout << "THE matrix is    " << '\n';
//	for(int i = 1;i <= n; i++){
//		for(int j = 1;j <= n; j++) cout << dp[i][j] << ' ';
//		cout << '\n';
//	}
//	cout << '\n' << '\n';
	for(int i = 1;i <= n; i++){
		for(int j = 1;j <= n; j++){
			dp[i][j]+= dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];

		}

	}
	
	
	
	for(int i = 1;i * i < n*n; i++){
		if(n%i==0){
			int j = n / i, need = 0;
			int col = 1, row = 1;
			for(int c = 1; c <= j; c++, row+= i, col = 1){
				if(c%2==1){
					for(int r = 1; r <= j; r++, col+= i){
						if(row + i-1 > n or col+i-1 > n) assert(false); 
						int black = get(row, col ,row+i-1, col+i-1);
//						if(i ==2)
//						cout << row << ' ' << col << " = " << black << '\n';
						int white = i*i - black;
						if(r%2==1){
							need+= black;
						}else{
							need+= white;
						}
					}					
				}else{
					for(int r = 1; r <= j; r++, col+= i){
						if(row + i-1 > n or col+i-1 > n) assert(false); 
						int black = get(row, col ,row+i-1, col+i-1);
//						if(i == 2)
//						cout << row << ' ' << col << " = " << black << '\n';
						int white = i*i - black;
						if(r%2==0){
							need+= black;
						}else{
							need+= white;
						}
					}
				}
			}
//			if(need == 14) cout << i << '\n';
			answer = min(answer, need);
			need = 0, col = 1, row = 1;
			for(int c = 1; c <= j; c++, row+= i, col = 1){
				if(c%2==0){
					for(int r = 1; r <= j; r++, col+= i){
						if(row + i-1 > n or col+i-1 > n) assert(false); 
						int black = get(row, col ,row+i-1, col+i-1);
						int white = i*i - black;
						if(r%2==1){
							need+= black;
						}else{
							need+= white;
						}
					}
				}else{
					for(int r = 1; r <= j; r++, col+= i){
						if(row + i-1 > n or col+i-1 > n) assert(false); 
						int black = get(row, col ,row+i-1, col+i-1);
						int white = i*i - black;
						if(r%2==0){
							need+= black;
						}else{
							need+= white;
						}
					}
				}
			}
			answer = min(answer, need);
		}
	}
	cout << answer;
	return 0;
}

Compilation message (stderr)

chessboard.cpp:38:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   38 | main(){
      | ^~~~

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