oj.uz

Submission #90332

# Submission time Handle Problem Language Result Execution time Memory
90332 2018-12-21T09:16:58 Z adlet Chessboard (IZhO18_chessboard) C++17
16 / 100
 110 ms 3396 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

using namespace std;

typedef long long ll;

#define int ll
#define y1 sda

const int N = 1e5 + 5;
const ll INF = 2e18;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);

int n, k;

ll ans = INF, k_area;

vector < int > v;

ll get(int x, int y, int xx, int yy, int len) {
    if (min({x, xx, y, yy}) < 0 || x > xx || y > yy)
        return 0;
    int f = ((x / len) % 2 == (y / len) % 2);
    x = (xx - x + 1) / len;
    y = (yy - y + 1) / len;
    ll num = (x * y) / 2;
    if (f) {
        num += ((x * y) % 2);
    }
    return num * len * len;
}

ll get_corner(int x, int y, int xx, int yy, int len) {
    if (min({x, xx, y, yy}) < 0 || x > xx || y > yy)
        return 0;
    int f = (((x / len) % 2) == ((y / len) % 2));
    x = (xx - x + 1);
    y = (yy - y + 1);
    ll num = (x * y) * f;
    return num;
}

int left(int l, int len) {
    return ((l + (len - 1)) / len) * len;
}

int right(int r, int len) {
    return (((r + 1) / len) * len) - 1;
}

ll get_sidex(int x, int y, int xx, int yy, int len) {
    if (min({x, xx, y, yy}) < 0 || x > xx || y > yy)
        return 0;
    int f = ((x / len) % 2) == ((y / len) % 2);
    y = yy - y + 1;
    x = (xx - x + 1) / len;
    ll num = (x / 2) + f * (x % 2);
    return num * y * len;
}

ll get_sidey(int x, int y, int xx, int yy, int len) {
    if (x > xx || y > yy)
        return 0;
    int f = ((x / len) % 2) == ((y / len) % 2);
    y = (yy - y + 1) / len;
    x = xx - x + 1;
    ll num = (y / 2) + f * (y % 2);
    return num * x * len;
}

ll get_one(int x, int y, int len) {
    return (((x / len) % 2) == ((y / len) % 2));
}

int x1[N], y1[N], x2[N], y2[N];

main() {
    cin >> n >> k;
    for (int i = 1; i <= k; ++i) {
        cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
        x1[i]--;
        y1[i]--;
        x2[i]--;
        y2[i]--;
        k_area += (y2[i] - y1[i] + 1) * (x2[i] - x1[i] + 1);
    }
    v.push_back(1);
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            v.push_back(i);
            if (n / i != i) {
                v.push_back(n / i);
            }
        }
    }
//    cout << k_area << "\n";
    for (int len : v) {
        int m = n / len, cnt_black = 0, cnt_white = 0;
        ll black = (((m * m) / 2) + ((m * m) % 2)) * (len * 1ll * len);
        ll white = (n * 1ll * n) - black;
//        cout << "\n" << len << " " << m << " " << black << " " << white << "\n";
        for (int j = 1; j <= k; ++j) {
//            if (x1[j] == x2[j] && y1[j] == y2[j]) {
//                cnt_black += get_one(x1[j], y1[j], i);
//            } else {
                int px1 = -1, px2 = -1, py1 = -1, py2 = -1;
                ll center_black = 0, corner_black = 0, side_black = 0;
                px1 = left(x1[j], len);
                py1 = left(y1[j], len);
                px2 = right(x2[j], len);
                py2 = right(y2[j], len);
                center_black = get(px1, py1, px2, py2, len);
                corner_black = get_corner(x1[j], y1[j], px1 - 1, py1 - 1, len) +
                               get_corner(px2 + 1, y1[j], x2[j], py1 - 1, len) +
                               get_corner(x1[j], py2 + 1, px1 - 1, y2[j], len) +
                               get_corner(px2 + 1, py2 + 1, x2[j], y2[j], len);
                side_black = get_sidex(px1, y1[j], px2, py1 - 1, len) + get_sidex(px1, py2 + 1, px2, y2[j], len) +
                             get_sidey(x1[j], py1, px1 - 1, py2, len) + get_sidey(px2 + 1, py1, x2[j], py2, len);
                cnt_black += center_black + corner_black + side_black;
//                cout << "\t" << j << " " << px1 << " " << py1 << " " << px2 << " " << py2 << "\n";
//                cout << x1[j] << " " << y1[j] << " " << x2[j] << " " << y2[j] << " " << center_black << " " << corner_black << " " << side_black << "\n";
//            }
        }
        cnt_white = k_area - cnt_black;
        ll fx = (black - cnt_black) + cnt_white;
        ll fy = (white - cnt_white) + cnt_black;
        if (fx < 0)
            fx = INF;
        if (fy < 0)
            fy = INF;
//        cout << cnt_black << " " << cnt_white << " " << fx << " " << fy << "\n\n";
        ans = min(ans, min(fx, fy));
    }
    cout << ans;
}

Compilation message

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

Subtask #1
8.0 / 8.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 2424 KB Output is correct
2 Correct 20 ms 2424 KB Output is correct
3 Correct 50 ms 2424 KB Output is correct
4 Correct 50 ms 2424 KB Output is correct
5 Correct 68 ms 2424 KB Output is correct
6 Correct 44 ms 2424 KB Output is correct
7 Correct 11 ms 2424 KB Output is correct
8 Correct 45 ms 2424 KB Output is correct
9 Correct 110 ms 3396 KB Output is correct
10 Correct 109 ms 3396 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 2424 KB Output is correct
2 Correct 20 ms 2424 KB Output is correct
3 Correct 50 ms 2424 KB Output is correct
4 Correct 50 ms 2424 KB Output is correct
5 Correct 68 ms 2424 KB Output is correct
6 Correct 44 ms 2424 KB Output is correct
7 Correct 11 ms 2424 KB Output is correct
8 Correct 45 ms 2424 KB Output is correct
9 Correct 110 ms 3396 KB Output is correct
10 Correct 109 ms 3396 KB Output is correct
11 Incorrect 2 ms 3396 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 376 KB Output is correct
2 Correct 2 ms 480 KB Output is correct
3 Correct 2 ms 480 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 2 ms 480 KB Output is correct
6 Correct 2 ms 480 KB Output is correct
7 Correct 2 ms 480 KB Output is correct
8 Correct 2 ms 480 KB Output is correct
9 Correct 79 ms 2424 KB Output is correct
10 Correct 20 ms 2424 KB Output is correct
11 Correct 50 ms 2424 KB Output is correct
12 Correct 50 ms 2424 KB Output is correct
13 Correct 68 ms 2424 KB Output is correct
14 Correct 44 ms 2424 KB Output is correct
15 Correct 11 ms 2424 KB Output is correct
16 Correct 45 ms 2424 KB Output is correct
17 Correct 110 ms 3396 KB Output is correct
18 Correct 109 ms 3396 KB Output is correct
19 Incorrect 2 ms 3396 KB Output isn't correct
20 Halted 0 ms 0 KB -