oj.uz

Submission #90895

# Submission time Handle Problem Language Result Execution time Memory
90895 2018-12-25T06:37:58 Z toloraia Chessboard (IZhO18_chessboard) C++14
0 / 100
 41 ms 2496 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll N = 1e5 + 5;

ll n, k;
ll x[N], y[N], X[N], Y[N];
ll a[2][2];
ll S1, S2;
ll ans;

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for (ll i = 1; i <= k; i++){
        cin>>x[i]>>y[i]>>X[i]>>Y[i];
        x[i]--;
        y[i]--;
        X[i]--;
        Y[i]--;
        S1 += (X[i] - x[i] + 1) * (Y[i] - y[i] + 1);
    }
    S2 = n * n - S1;
    ans = n * n;
    for (ll I = 1; I <= n; I++)
        if (n % I == 0){
            ll s1 = ((n / I) * (n / I) + 1) / 2 * I * I, s2 = (n / I) * (n / I) / 2 * I * I;
            ll m1 = 0, m2 = 0;
            for (ll i = 1; i <= k; i++){
                for (ll j = 0; j < 2; j++)
                    for (ll l = 0; l < 2; l++)
                        a[j][l] = 0;
                ll p, q, t;
                p = (x[i] + I - 1) / I * I;
                if (X[i] < p)
                    a[0][(x[i] / I) % 2] += X[i] - x[i] + 1;
                else {
                    q = X[i] / I * I;
                    t = (q - p) / I;
                    a[0][(x[i] / I) % 2] += p - x[i];
                    a[0][(X[i] / I) % 2] += X[i] - q + 1;
                    a[0][(p / I) % 2] += (t + 1) / 2 * I;
                    a[0][(p / I + 1) % 2] += t / 2 * I;
                }
                p = (y[i] + I - 1) / I * I;
                if (Y[i] < p)
                    a[1][(y[i] / I) % 2] += Y[i] - y[i] + 1;
                else {
                    q = Y[i] / I * I;
                    t = (q - p) / I;
                    a[1][(y[i] / I) % 2] += p - y[i];
                    a[1][(Y[i] / I) % 2] += Y[i] - q + 1;
                    a[1][(p / I) % 2] += (t + 1) / 2 * I;
                    a[1][(p / I + 1) % 2] += t / 2 * I;
                }
                m1 += a[0][0] * a[1][0] + a[0][1] * a[1][1];
                m2 += a[0][0] * a[1][1] + a[0][1] * a[1][0];
            }
            ll pas = 0;
            pas = n * n - m1 - min (s2 - m2, S2);
            ans = min (ans, pas);
            pas = n * n - m2 - min (s2 - m1, S1);
            ans = min (ans, pas);
        }
    cout<<ans<<endl;
    return 0;
}

Compilation message

chessboard.cpp: In function 'int main()':
chessboard.cpp:29:16: warning: unused variable 's1' [-Wunused-variable]
             ll s1 = ((n / I) * (n / I) + 1) / 2 * I * I, s2 = (n / I) * (n / I) / 2 * 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 508 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 15.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2496 KB Output is correct
2 Incorrect 12 ms 2496 KB Output isn't correct
3 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 508 KB Output isn't correct
3 Halted 0 ms 0 KB -