oj.uz

Submission #173860

# Submission time Handle Problem Language Result Execution time Memory
173860 2020-01-05T15:34:20 Z VEGAnn Chessboard (IZhO18_chessboard) C++14
8 / 100
 54 ms 3896 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pii pair<int, int>
#define ft first
#define sd second
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
const int oo = 2e9;
const ll OO = 1e18;
const int N = 100100;
ll ans = OO, gl;
int x1[N], Y1[N], x2[N], y2[N], n, k;

ll calc(ll x, ll y){
    if (x <= 0 || y <= 0) return 0;
    ll kl = y / gl, res = 0;
    ll ko = x / gl;

    ll ad1 = 0, ad2 = 0;

    if (x % gl > 0){
        if (ko % 2 == 0)
            ad1 += x % gl;
        else ad2 += x % gl;
    }

    res += ((kl + 1) / 2ll) * gl * ((ko + 1) / 2ll * gl + ad1);
    res += ((kl + 0) / 2ll) * gl * ((ko + 0) / 2ll * gl + ad2);

    if (y % gl > 0){
        if (kl % 2 == 0)
            res += ((ko + 1) / 2ll * gl + ad1) * (y % gl);
        else res += ((ko + 0) / 2ll * gl + ad2) * (y % gl);
    }

    return res;
}

ll calc(ll x1, ll Y1, ll x2, ll y2){
    return calc(x2, y2) - calc(x1 - 1, y2) - calc(x2, Y1 - 1) + calc(x1 - 1, Y1 - 1);
}

ll check(ll x){
    gl = x;
    ll cnd1 = calc(n, n);
    ll cnd2 = ll(n) * ll(n) - cnd1;

    for (int i = 0; i < k; i++){
        ll k1 = calc(x1[i], Y1[i], x2[i], y2[i]);
        ll x = x2[i] - x1[i] + 1;
        ll y = y2[i] - Y1[i] + 1;
        cnd1 -= k1 - (x * y - k1);
        cnd2 -= - k1 + (x * y - k1);
    }

    return min(cnd1, cnd2);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> k;
    for (int i = 0; i < k; i++)
        cin >> x1[i] >> Y1[i] >> x2[i] >> y2[i];

    int root = (int)trunc(sqrt(n));
    for (int i = 1; i <= root; i++)
        if (n % i == 0){
            ans = min(ans, check(i));
            if (i != i)
                ans = min(ans, check(n / i));
        }

    cout << ans;

    return 0;
}

Compilation message

chessboard.cpp: In function 'int main()':
chessboard.cpp:72:19: warning: self-comparison always evaluates to false [-Wtautological-compare]
             if (i != i)
                 ~~^~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2936 KB Output is correct
2 Correct 12 ms 1144 KB Output is correct
3 Correct 19 ms 1912 KB Output is correct
4 Correct 23 ms 2040 KB Output is correct
5 Correct 34 ms 2444 KB Output is correct
6 Correct 22 ms 1784 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Correct 23 ms 1784 KB Output is correct
9 Correct 54 ms 3896 KB Output is correct
10 Correct 31 ms 2296 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2936 KB Output is correct
2 Correct 12 ms 1144 KB Output is correct
3 Correct 19 ms 1912 KB Output is correct
4 Correct 23 ms 2040 KB Output is correct
5 Correct 34 ms 2444 KB Output is correct
6 Correct 22 ms 1784 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Correct 23 ms 1784 KB Output is correct
9 Correct 54 ms 3896 KB Output is correct
10 Correct 31 ms 2296 KB Output is correct
11 Incorrect 2 ms 376 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 Incorrect 2 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -