oj.uz

Submission #102005

# Submission time Handle Problem Language Result Execution time Memory
102005 2019-03-21T12:46:59 Z naoai Ideal city (IOI12_city) C++14
55 / 100
 214 ms 16108 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long i64;
const int mod = 1e9;
const int nmax = 1e5;

const int dl[4] = {-1, 0, 0, 1};
const int dc[4] = {0, -1, 1, 0};

queue<pair<int, int>> q;
bool viz[2000 + 1];

int ind[2000 + 1][2000 + 1];

int brut (int N, int *X, int *Y) {
    int mnx = 1 << 30;
    int mny = 1 << 30;

    for (int i = 0; i < N; ++ i) {
        mnx = min(mnx, X[i]);
        mny = min(mny, Y[i]);
    }

    for (int i = 0; i < N +1; ++ i)
        for (int j = 0; j < N + 1; ++ j)
            ind[i][j] = -1;

    for (int i = 0; i < N; ++ i) {
        X[i] -= (mnx - 1);
        Y[i] -= (mny - 1);
        ind[X[i]][Y[i]] = i;
    }

    i64 ans = 0;
    for (int i = 0; i < N; ++ i) {
        memset(viz, 0, sizeof(viz));
        q.push({i, 0});
        viz[i] = 1;

        while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            ans += y;

            for (int k = 0; k <4; ++ k) {
                int a = X[x] + dl[k], b = Y[x] + dc[k];
                if (ind[a][b] != -1) {
                    int t = ind[a][b];
                    if (viz[t] == 1)
                        continue;

                    viz[t] = 1;
                    q.push({t, y + 1});
                }
            }
        }
    }

    ans /= 2;
    return ans % mod;
}

i64 solve (vector<int> &v) {
    sort(v.begin(), v.end());

    i64 ans = 0;
    i64 sum = 0;
    for (auto i : v)
        sum += i;

    i64 m = 0;
    for (int i = 0; i < v.size(); ++ i) {
        sum -= v[i];

        ans += 1LL * v[i] * i - m + sum - 1LL * v[i] * (v.size() - 1 - i);

        m += v[i];
    }
    return ans;
}

int DistanceSum(int N, int *X, int *Y) {
    if (N <= 2000) {
        return brut(N, X, Y);
    } else {
        i64 ans = 0;

        vector<int> v;
        for (int i = 0; i < N; ++ i)
            v.push_back(X[i]);
        ans += solve(v);

        v.clear();
        for (int i = 0; i < N; ++ i)
            v.push_back(Y[i]);
        ans += solve(v);

        return (ans / 2) % mod;
    }
}

Compilation message

city.cpp: In function 'i64 solve(std::vector<int>&)':
city.cpp:75:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++ i) {
                     ~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 768 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 5 ms 1280 KB Output is correct
7 Correct 4 ms 1280 KB Output is correct
8 Correct 4 ms 1280 KB Output is correct
9 Correct 5 ms 1280 KB Output is correct
10 Correct 4 ms 1280 KB Output is correct
11 Correct 4 ms 1280 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 8228 KB Output is correct
2 Correct 47 ms 8192 KB Output is correct
3 Correct 117 ms 12280 KB Output is correct
4 Correct 89 ms 12160 KB Output is correct
5 Correct 184 ms 16108 KB Output is correct
6 Correct 122 ms 16080 KB Output is correct
7 Correct 214 ms 16088 KB Output is correct
8 Correct 140 ms 16092 KB Output is correct
9 Correct 112 ms 16000 KB Output is correct
10 Correct 122 ms 16000 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 768 KB Output is correct
2 Correct 8 ms 768 KB Output is correct
3 Correct 22 ms 1152 KB Output is correct
4 Correct 17 ms 1280 KB Output is correct
5 Correct 34 ms 1792 KB Output is correct
6 Correct 33 ms 1784 KB Output is correct
7 Correct 37 ms 1792 KB Output is correct
8 Correct 32 ms 1792 KB Output is correct
9 Correct 33 ms 1912 KB Output is correct
10 Correct 33 ms 1764 KB Output is correct

Subtask #4
0 / 45.0

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