oj.uz

Submission #155163

# Submission time Handle Problem Language Result Execution time Memory
155163 2019-09-26T18:04:36 Z srvlt Chessboard (IZhO18_chessboard) C++14
8 / 100
 30 ms 1400 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse2,avx")
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
//#define int long long
using namespace std;

void dout() {
    cerr << endl;
}

template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e5 + 3;
const ll inf = 1e18;

int k, p[2][N], rx[N], ry[N], rx2[N], ry2[N];
ll n, ans = inf, A, Z, S, W, sq_A;

int color(int x, int y) {
    int z = (x - 1) / A;
    int w = (y - 1) / A;
    return ((z + w + Z) & 1);
}

int num(int x) {
    int z = (x - 1) / A;
    return (z & 1);
}

ll getL() {
    int x = n / A;
    ll a = ((x + 1) >> 1LL) * sq_A;
    ll b = (x >> 1LL) * sq_A;
    ll res = ((x + 1) >> 1LL) * a + (x >> 1LL) * b;
    if (Z == 0) {
        return res;
    }   else {
        return n * n - res;
    }
}

ll getval(int x, int a, int b) {
    if (x < 1) {
        return 0;
    }
    ll res = 0;
    int q = (x - 1) / A;
    int last = q * A + 1;
    if (num(last) == 0) {
        res += (x - last + 1) * a;
    }   else {
        res += (x - last + 1) * b;
    }
    res += (((q + 1) >> 1LL) * a + (q >> 1LL) * b) * A;
    return res;
}

ll getans() {
    for (int i = 1; i <= n; i++) {
        p[0][i] = p[0][i - 1];
        p[1][i] = p[1][i - 1];
        if (color(i, 1)) {
            p[0][i]++;
        }   else {
            p[1][i]++;
        }
    }
    ll res = 0;
    for (int i = 0; i < k; i++) {
        int v1 = p[0][rx2[i]] - p[0][rx[i] - 1];
        int v2 = p[1][rx2[i]] - p[1][rx[i] - 1];
        res += getval(ry2[i], v1, v2) - getval(ry[i] - 1, v1, v2);
    }
    return res;
}

void solve(int tc) {
    cin >> n >> k;
    for (int i = 0; i < k; i++) {
        cin >> rx[i] >> ry[i] >> rx2[i] >> ry2[i];
        S += (ll)(rx2[i] - rx[i] + 1) * (ry2[i] - ry[i] + 1);
    }
    vector <int> factors = {};
    for (int i = 1; i < n; i++) {
        if (n % i == 0) {
            factors.pb(i);
        }
    }
    for (auto i : factors) {
        A = i;
        sq_A = A * A;
        for (int j = 0; j < 2; j++) {
            Z = j;
            ans = min(ans, W + W + getL() - S);
        }
    }
    cout << ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int tc = 1;
//    cin >> tc;
    for (int i = 0; i < tc; i++) {
        solve(i);
//        cleanup();
    }
}

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 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 15.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 1400 KB Output isn't correct
2 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 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Incorrect 30 ms 1400 KB Output isn't correct
10 Halted 0 ms 0 KB -