oj.uz

답안 #90308

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
90308 2018-12-21T08:28:16 Z adlet Chessboard (IZhO18_chessboard) C++17
0 / 100
 75 ms 2404 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 = 1e18;
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 (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 (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 (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 i : v) {
        int m = n / i, cnt_black = 0, cnt_white = 0;
        ll black = (((m * m) / 2) + ((m * m) % 2)) * (i * 1ll * i);
        ll white = (n * 1ll * n) - black;
//        cout << i << " " << 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], i);
                py1 = left(y1[j], i);
                px2 = right(x2[j], i);
                py2 = right(y2[j], i);
                center_black = get(px1, py1, px2, py2, i);
                corner_black = get_corner(x1[j], y1[j], px1 - 1, py1 - 1, i) +
                               get_corner(px2 + 1, y1[j], x2[j], py1 - 1, i) +
                               get_corner(x1[j], py2 + 1, px1 - 1, y2[j], i) +
                               get_corner(px2 + 1, py2 + 1, x2[j], y2[j], i);
                side_black = get_sidex(px1, y1[j], px2, py1 - 1, i) + get_sidex(px1, py2 + 1, px2, y2[j], i) +
                             get_sidey(x1[j], py1, px1 - 1, py2, i) + get_sidey(px2 + 1, py1, x2[j], py2, i);
                cnt_black += center_black + corner_black + side_black;
            }
        }
        cnt_white = k_area - cnt_black;
        ll fx = (black - cnt_black) + cnt_white;
        ll fy = (white - cnt_white) + cnt_black;
//        cout << cnt_black << " " << cnt_white << " " << fx << " " << fy << "\n\n";
        ans = min(ans, min(fx, fy));
    }
    cout << ans;
}

Compilation message

chessboard.cpp: In function 'll get_sidey(ll, ll, ll, ll, ll)':
chessboard.cpp:66:11: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
     if (x > xx | y > yy)
         ~~^~~~
chessboard.cpp: At global scope:
chessboard.cpp:81:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 75 ms 2404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 75 ms 2404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -