oj.uz

Submission #682836

# Submission time Handle Problem Language Result Execution time Memory
682836 2023-01-17T05:45:01 Z iskhakkutbilim Chessboard (IZhO18_chessboard) C++14
16 / 100
 95 ms 7992 KB 
#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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3028 KB Output is correct
8 Correct 3 ms 3036 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 6984 KB Output is correct
2 Correct 20 ms 3724 KB Output is correct
3 Correct 53 ms 6092 KB Output is correct
4 Correct 40 ms 4880 KB Output is correct
5 Correct 60 ms 6508 KB Output is correct
6 Correct 39 ms 5424 KB Output is correct
7 Correct 9 ms 3308 KB Output is correct
8 Correct 35 ms 5276 KB Output is correct
9 Correct 95 ms 7992 KB Output is correct
10 Correct 61 ms 5944 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3044 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 3044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 6984 KB Output is correct
2 Correct 20 ms 3724 KB Output is correct
3 Correct 53 ms 6092 KB Output is correct
4 Correct 40 ms 4880 KB Output is correct
5 Correct 60 ms 6508 KB Output is correct
6 Correct 39 ms 5424 KB Output is correct
7 Correct 9 ms 3308 KB Output is correct
8 Correct 35 ms 5276 KB Output is correct
9 Correct 95 ms 7992 KB Output is correct
10 Correct 61 ms 5944 KB Output is correct
11 Incorrect 2 ms 3044 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 2652 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3028 KB Output is correct
8 Correct 3 ms 3036 KB Output is correct
9 Correct 68 ms 6984 KB Output is correct
10 Correct 20 ms 3724 KB Output is correct
11 Correct 53 ms 6092 KB Output is correct
12 Correct 40 ms 4880 KB Output is correct
13 Correct 60 ms 6508 KB Output is correct
14 Correct 39 ms 5424 KB Output is correct
15 Correct 9 ms 3308 KB Output is correct
16 Correct 35 ms 5276 KB Output is correct
17 Correct 95 ms 7992 KB Output is correct
18 Correct 61 ms 5944 KB Output is correct
19 Incorrect 2 ms 3044 KB Output isn't correct
20 Halted 0 ms 0 KB -