oj.uz

Submission #573355

# Submission time Handle Problem Language Result Execution time Memory
573355 2022-06-06T12:51:33 Z kenjinemera Ideal city (IOI12_city) C++17
0 / 100
 4 ms 596 KB 
#include <bits/stdc++.h>

using namespace std;

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

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

    int pref[sz+1];

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

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

    int 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];
    }

    int ans = 0;

    for (int i = 0; i < sz; i++)
    {
        ans += arr[i] * 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++;
    }

    int ans = (solve(listx) + solve(listy)) % (1000000000);

    return ans;
}

// WHEN SUBMITTING PROGRAMMES WITH A METHOD SIGNATURE -> USE MAIN TO TEST
//int main()
//{
//    int n;
//
//    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 0 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 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

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

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 -