답안 #667813

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
667813	2022-12-02T05:32:35 Z	Kaztaev_Alisher	Chessboard (IZhO18_chessboard)	C++17	16 / 100	27 ms	1620 KB

chessboard

//#pragma GCC optomize ("Ofast")
//#pragma GCC optomize ("unroll-loops")
//#pragma GCC target ("avx,avx2,fma")

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define sz size
#define cl clear
#define ins insert
#define ers erase
#define pii pair < int , int >
#define pll pair< long long  , long long >
#define all(x) x.begin() , x.end()
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define tostr(x) to_string(x)
#define tonum(s) atoi(s.c_str())
#define seon(x) setprecision(x)
#define bpop(x) __builtin_popcount(x)
#define deb(x) cerr << #x  << " = " << x << endl;
#define int ll

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
const double PI = 3.14159265;

const ll N = 1e6+5 , M = 2e3+5;
const ll mod = 1e9+7;
const ll inf = 1e9;
const ll INF = 1e18;

using namespace std;

int n;
bool u[N];
int dp[M][M];
ll check(int k){
	int cnt0 = 0 , cnt1 = 0;
	int cnt10 = 0 , cnt11 = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if((i/k)%2==(j/k)%2) {
				if(dp[i][j] == 1) cnt1++;
				else cnt0++;
			} else {
				if(dp[i][j] == 1) cnt11++;
				else cnt10++;
			}
		}
	}
	return min(cnt0+cnt11 , cnt10+cnt1);
}
void solve(){
	ll k;
	cin >> n >> k;
	if(u[n] == 0){
		ll cnt = 0 , cnt1 = 0;
		for(int i = 1; i <= k; i++){
			ll x , y , x1 , y1;
			cin >> x >> y >> x1 >> y1;
			if(x % 2 == y % 2) cnt++;
			else cnt1++;
		}
		cout << min((n*n+1)/2-cnt+cnt1 , n*n/2-cnt1+cnt) <<"\n";
		return;
	} else {
		for(int i = 1; i <= k; i++){
			ll x , y , x1 , y1;
			cin >> x >> y >> x1 >> y1;
			x--;
			y--;
			dp[x][y] = 1;
		}
		ll mn = INF;
		for(int i = 1; i <= sqrtl(n); i++){
			if(n*n % i == 0){
				mn = min(mn , check(i));
				if(i > 1) mn = min(mn , check(n/i));
			}
		}
		cout << mn <<"\n";
	}
}
signed main(){
	ios;
	for(int i = 2; i <= N-5; i++){
		if(u[i] == 1) continue;
		for(ll j = i*i; j <= N-5; j+=i) u[j] = 1;
	}
	solve();
	return 0;
}
/*
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
*/

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1236 KB	Output is correct
2	Correct	4 ms	1236 KB	Output is correct
3	Correct	3 ms	1300 KB	Output is correct
4	Correct	4 ms	1236 KB	Output is correct
5	Correct	3 ms	1300 KB	Output is correct
6	Correct	3 ms	1236 KB	Output is correct
7	Correct	3 ms	1300 KB	Output is correct
8	Correct	3 ms	1236 KB	Output is correct

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	1288 KB	Output is correct
2	Correct	7 ms	1236 KB	Output is correct
3	Correct	13 ms	1312 KB	Output is correct
4	Correct	13 ms	1236 KB	Output is correct
5	Correct	17 ms	1304 KB	Output is correct
6	Correct	15 ms	1236 KB	Output is correct
7	Correct	6 ms	1308 KB	Output is correct
8	Correct	12 ms	1236 KB	Output is correct
9	Correct	27 ms	1304 KB	Output is correct
10	Correct	17 ms	1236 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1620 KB	Output is correct
2	Correct	3 ms	1364 KB	Output is correct
3	Correct	3 ms	1492 KB	Output is correct
4	Correct	4 ms	1564 KB	Output is correct
5	Correct	3 ms	1620 KB	Output is correct
6	Correct	4 ms	1620 KB	Output is correct
7	Correct	5 ms	1620 KB	Output is correct
8	Correct	5 ms	1492 KB	Output is correct
9	Correct	4 ms	1620 KB	Output is correct
10	Correct	3 ms	1236 KB	Output is correct
11	Correct	3 ms	1492 KB	Output is correct
12	Correct	3 ms	1236 KB	Output is correct
13	Correct	3 ms	1492 KB	Output is correct
14	Incorrect	5 ms	1552 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #4
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1620 KB	Output is correct
2	Correct	3 ms	1364 KB	Output is correct
3	Correct	3 ms	1492 KB	Output is correct
4	Correct	4 ms	1564 KB	Output is correct
5	Correct	3 ms	1620 KB	Output is correct
6	Correct	4 ms	1620 KB	Output is correct
7	Correct	5 ms	1620 KB	Output is correct
8	Correct	5 ms	1492 KB	Output is correct
9	Correct	4 ms	1620 KB	Output is correct
10	Correct	3 ms	1236 KB	Output is correct
11	Correct	3 ms	1492 KB	Output is correct
12	Correct	3 ms	1236 KB	Output is correct
13	Correct	3 ms	1492 KB	Output is correct
14	Incorrect	5 ms	1552 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #5
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	1288 KB	Output is correct
2	Correct	7 ms	1236 KB	Output is correct
3	Correct	13 ms	1312 KB	Output is correct
4	Correct	13 ms	1236 KB	Output is correct
5	Correct	17 ms	1304 KB	Output is correct
6	Correct	15 ms	1236 KB	Output is correct
7	Correct	6 ms	1308 KB	Output is correct
8	Correct	12 ms	1236 KB	Output is correct
9	Correct	27 ms	1304 KB	Output is correct
10	Correct	17 ms	1236 KB	Output is correct
11	Correct	3 ms	1620 KB	Output is correct
12	Correct	3 ms	1364 KB	Output is correct
13	Correct	3 ms	1492 KB	Output is correct
14	Correct	4 ms	1564 KB	Output is correct
15	Correct	3 ms	1620 KB	Output is correct
16	Correct	4 ms	1620 KB	Output is correct
17	Correct	5 ms	1620 KB	Output is correct
18	Correct	5 ms	1492 KB	Output is correct
19	Correct	4 ms	1620 KB	Output is correct
20	Correct	3 ms	1236 KB	Output is correct
21	Correct	3 ms	1492 KB	Output is correct
22	Correct	3 ms	1236 KB	Output is correct
23	Correct	3 ms	1492 KB	Output is correct
24	Incorrect	5 ms	1552 KB	Output isn't correct
25	Halted	0 ms	0 KB	-

Subtask #6
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1236 KB	Output is correct
2	Correct	4 ms	1236 KB	Output is correct
3	Correct	3 ms	1300 KB	Output is correct
4	Correct	4 ms	1236 KB	Output is correct
5	Correct	3 ms	1300 KB	Output is correct
6	Correct	3 ms	1236 KB	Output is correct
7	Correct	3 ms	1300 KB	Output is correct
8	Correct	3 ms	1236 KB	Output is correct
9	Correct	23 ms	1288 KB	Output is correct
10	Correct	7 ms	1236 KB	Output is correct
11	Correct	13 ms	1312 KB	Output is correct
12	Correct	13 ms	1236 KB	Output is correct
13	Correct	17 ms	1304 KB	Output is correct
14	Correct	15 ms	1236 KB	Output is correct
15	Correct	6 ms	1308 KB	Output is correct
16	Correct	12 ms	1236 KB	Output is correct
17	Correct	27 ms	1304 KB	Output is correct
18	Correct	17 ms	1236 KB	Output is correct
19	Correct	3 ms	1620 KB	Output is correct
20	Correct	3 ms	1364 KB	Output is correct
21	Correct	3 ms	1492 KB	Output is correct
22	Correct	4 ms	1564 KB	Output is correct
23	Correct	3 ms	1620 KB	Output is correct
24	Correct	4 ms	1620 KB	Output is correct
25	Correct	5 ms	1620 KB	Output is correct
26	Correct	5 ms	1492 KB	Output is correct
27	Correct	4 ms	1620 KB	Output is correct
28	Correct	3 ms	1236 KB	Output is correct
29	Correct	3 ms	1492 KB	Output is correct
30	Correct	3 ms	1236 KB	Output is correct
31	Correct	3 ms	1492 KB	Output is correct
32	Incorrect	5 ms	1552 KB	Output isn't correct
33	Halted	0 ms	0 KB	-

답안 #667813

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 8.0 / 8.0

Subtask #3 0 / 15.0

Subtask #4 0 / 16.0

Subtask #5 0 / 23.0

Subtask #6 0 / 30.0

Subtask #1
8.0 / 8.0

Subtask #2
8.0 / 8.0

Subtask #3
0 / 15.0

Subtask #4
0 / 16.0

Subtask #5
0 / 23.0

Subtask #6
0 / 30.0