oj.uz

Submission #523573

# Submission time Handle Problem Language Result Execution time Memory
523573 2022-02-07T19:49:06 Z RaresFelix Chessboard (IZhO18_chessboard) C++17
39 / 100
 155 ms 2144 KB 
#include <iostream>
#include <climits>
#include <tuple>
#include <vector>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define MN 107171

using namespace std;
using ll = long long;
ll n, k;
tuple<int, int, int, int> R[MN];
int P[MN], D[MN];
int P2[MN], D2[MN];
static inline ll calc(ll a, ll b, ll l) {
    if(P[a] == 0 && P[b] == 0)
        return ((D[a] * D[b] + 1) >> 1) * l * l;
    if(P[a]) {
        ll nrseg;
        if((D[a] & 1) == 0) {
            if(P2[b] <= l) nrseg = D2[b] * l + P2[b];
            else nrseg = (D2[b] + 1) * l;
        } else {
            if(P2[b] <= l) nrseg = D2[b] * l;
            else nrseg = (D2[b] - 1) * l + P2[b];
        }
        return calc(a - P[a], b, l) + P[a] * nrseg;
    }
    return calc(b, a, l);
}
ll sol(ll l) {
    for(int i = 1; i <= n; ++i) {
        D[i] = D[i-1];
        P[i] = P[i-1] + 1;
        if(P[i] == l) ++D[i], P[i] = 0;
        D2[i] = D2[i-1];
        P2[i] = P2[i-1] + 1;
        if(P2[i] == (l << 1)) ++D2[i], P2[i] = 0;
    }
    ll arie = ((n / l) * (n / l) + 1) / 2 * l * l, selec;
    for(int i = 1; i <= k; ++i) {
        auto &[a, b, c, d] = R[i];
        selec = calc(c, d, l) + calc(a-1, b-1, l) - calc(c, b-1, l) - calc(a-1, d, l);
        arie += (c - a + 1) * (d - b + 1) - 2 * selec;
    }
    return min(arie, 1ll * n * n - arie);
}
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> n >> k;
    for(int i = 1, a, b, c, d; i <= k; ++i)
        cin >> a >> b >> c >> d, R[i] = make_tuple(a, b, c, d);
    ll re = LLONG_MAX;
    for(int i = 1; i < n; ++i)
        if(n % i == 0) re = min(re, sol(i));
    cout << re << "\n";
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 2144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 272 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 272 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 10 ms 716 KB Output is correct
17 Correct 31 ms 1532 KB Output is correct
18 Correct 35 ms 1860 KB Output is correct
19 Correct 139 ms 1604 KB Output is correct
20 Correct 155 ms 1868 KB Output is correct
21 Correct 27 ms 1544 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 34 ms 908 KB Output is correct
24 Correct 31 ms 1760 KB Output is correct
25 Correct 6 ms 480 KB Output is correct
26 Correct 19 ms 1228 KB Output is correct
27 Correct 30 ms 1412 KB Output is correct
28 Correct 33 ms 1740 KB Output is correct
29 Correct 8 ms 844 KB Output is correct
30 Correct 1 ms 332 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 2144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Incorrect 20 ms 2144 KB Output isn't correct
10 Halted 0 ms 0 KB -