#include <bits/stdc++.h>
#define pb push_back
#define LL long long
#define Kultivator ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int LL
using namespace std;
const LL Mxn = 1e6 + 7;
const LL Mod = 1e9 + 7;
const LL Inf = 1e14 + 7;
bool Prime(int N){
bool Used = false;
for(int i = 2; i <= sqrt(N); i++){
if(N % i == 0){
Used = true;
break;
}
}
return Used;
}
bool Get(int x, int y, int d){
return (x / d + y / d) % 2;
}
void Ans1(int N){
int Ans = Mxn;
for(int i = 1; i < N; i++){
if(N % i == 0){
Ans = min(Ans, (N * N) / (2 * i * i) * (i * i));
}
}
cout << Ans;
}
void Ans2(int N, int K){
LL Cnt1 = 0, Cnt2 = 0;
for(int i = 1, x1, y1, x2, y2; i <= K; i++){
cin >> x1 >> y1 >> x2 >> y2;
bool Num = Get(x2, y2, 1);
if(!Num){
Cnt1++;
} else {
Cnt2++;
}
}
cout << min(N * N / 2 - Cnt2 + Cnt1, N * N / 2 + 1 - Cnt1 + Cnt2);
}
void Ans3(int N, int K){
int Ans = LONG_MAX;
vector <int> F;
vector <pair <int, int>> P;
for(int i = 2; i <= sqrt(N); i++){
if(N % i == 0){
F.pb(i);
if(N / i != i){
F.pb(N / i);
}
}
}
for(int i = 1, x1, y1, x2, y2; i <= K; i++){
cin >> x1 >> y1 >> x2 >> y2;
for(auto i : F){
if(Get(x1, y1, i)){
P[i].second++;
} else {
P[i].first++;
}
}
}
for(auto i : F){
Ans = min(Ans, ((N * N) / 2) + (i * i) + P[i].first - P[i].second);
Ans = min(Ans, ((N * N) / 2) - P[i].first + P[i].second);
}
cout << Ans;
}
signed main(){
Kultivator;
LL N, K;
cin >> N >> K;
if(!K){
Ans1(N);
} else if(!Prime(N)){
Ans2(N, K);
} else {
Ans3(N, K);
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
0 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
0 ms |
364 KB |
Output is correct |
7 |
Correct |
0 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
364 KB |
Output is correct |
2 |
Correct |
6 ms |
364 KB |
Output is correct |
3 |
Correct |
16 ms |
364 KB |
Output is correct |
4 |
Correct |
16 ms |
364 KB |
Output is correct |
5 |
Correct |
20 ms |
364 KB |
Output is correct |
6 |
Correct |
13 ms |
364 KB |
Output is correct |
7 |
Correct |
3 ms |
364 KB |
Output is correct |
8 |
Correct |
13 ms |
364 KB |
Output is correct |
9 |
Correct |
32 ms |
364 KB |
Output is correct |
10 |
Correct |
19 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
364 KB |
Output is correct |
2 |
Correct |
6 ms |
364 KB |
Output is correct |
3 |
Correct |
16 ms |
364 KB |
Output is correct |
4 |
Correct |
16 ms |
364 KB |
Output is correct |
5 |
Correct |
20 ms |
364 KB |
Output is correct |
6 |
Correct |
13 ms |
364 KB |
Output is correct |
7 |
Correct |
3 ms |
364 KB |
Output is correct |
8 |
Correct |
13 ms |
364 KB |
Output is correct |
9 |
Correct |
32 ms |
364 KB |
Output is correct |
10 |
Correct |
19 ms |
364 KB |
Output is correct |
11 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
0 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
0 ms |
364 KB |
Output is correct |
7 |
Correct |
0 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
23 ms |
364 KB |
Output is correct |
10 |
Correct |
6 ms |
364 KB |
Output is correct |
11 |
Correct |
16 ms |
364 KB |
Output is correct |
12 |
Correct |
16 ms |
364 KB |
Output is correct |
13 |
Correct |
20 ms |
364 KB |
Output is correct |
14 |
Correct |
13 ms |
364 KB |
Output is correct |
15 |
Correct |
3 ms |
364 KB |
Output is correct |
16 |
Correct |
13 ms |
364 KB |
Output is correct |
17 |
Correct |
32 ms |
364 KB |
Output is correct |
18 |
Correct |
19 ms |
364 KB |
Output is correct |
19 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
20 |
Halted |
0 ms |
0 KB |
- |