oj.uz

Submission #573413

# Submission time Handle Problem Language Result Execution time Memory
573413 2022-06-06T14:55:47 Z kenjinemera Ideal city (IOI12_city) C++17
23 / 100
 22 ms 2720 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100001; 
int ax[MAXN], ay[MAXN];
const int MOD = 1000000000;

long long solve(vector<int> arr)
{
    // build prefix
    int sz = arr.size();

    long long pref[sz+1];

    fill(pref, pref + sz + 1, 0);

    for (int i = sz - 1; i >= 0; i--)
    {
        pref[i] = arr[i] + pref[i + 1];
    }

    long long inc_pref[sz+1];

    fill(inc_pref, inc_pref + sz + 1, 0);

    for (int i = sz - 1; i >= 0; i--)
    {
        inc_pref[i] = pref[i] + inc_pref[i+1];
    }

    long long ans = 0;

    for (int i = 0; i < sz; i++)
    {
        ans += (long long) arr[i] * (long long) inc_pref[i + 1];    
    }

    return ans;
}

int DistanceSum(int N, int *X, int *Y)
{
    // given our grid we can build a stack of nodes at each occupied x and y value.
    int startx = INT_MAX, starty = INT_MAX;

    for (int i = 0; i < N; i++)
    {   
        startx = min(startx, X[i]);
        starty = min(starty, Y[i]);

        ax[X[i]]++;
        ay[Y[i]]++;
    }

    // loop over each cell that is stacked and create a list of nodes
    int cur = startx;
    
    vector<int> listx;
    while (ax[cur])
    {
        listx.push_back(ax[cur]);
        cur++;
    }

    cur = starty;
    vector<int> listy;

    while (ay[cur])
    {
        listy.push_back(ay[cur]);
        cur++;
    }

    long long ans = (solve(listx) + solve(listy)) % MOD;

    return ans;
}

// WHEN SUBMITTING PROGRAMMES WITH A METHOD SIGNATURE -> USE MAIN TO TEST
//int main()
//{
//    int n;
//
//    freopen("input.txt", "r", stdin);
//
//    cin >> n;
//
//    int x[n];
//    int y[n];
//
//    for (int i = 0; i < n; i++)
//    {
//        cin >> x[i] >> y[i];
//    }
//
//    cout << DistanceSum(n, x, y) << "\n";
//
//    return 0;
//}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 3 ms 568 KB Output is correct
3 Correct 10 ms 1088 KB Output is correct
4 Correct 8 ms 1108 KB Output is correct
5 Correct 17 ms 1864 KB Output is correct
6 Correct 17 ms 1876 KB Output is correct
7 Correct 19 ms 2080 KB Output is correct
8 Correct 18 ms 1864 KB Output is correct
9 Correct 18 ms 1968 KB Output is correct
10 Correct 22 ms 2720 KB Output is correct

Subtask #4
0 / 45.0

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