Submission #682836

#	Time	Username	Problem	Language	Result	Execution time	Memory
682836		iskhakkutbilim	Chessboard (IZhO18_chessboard)	C++14	16 / 100	95 ms	7992 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][y1] - dp[x1][y]+dp[x][y];
}

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;
	}
	for(int i = 0;i < n; i++){
		for(int j = 0;j < n; j++){
			dp[i+1][j+1]+= dp[i][j+1]+dp[i+1][j]-dp[i][j];
		}
	}
	
	
	
	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);
						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);
			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:25:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   25 | main(){
      | ^~~~

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