oj.uz

Submission #1003736

# Submission time Handle Problem Language Result Execution time Memory
1003736 2024-06-20T16:33:44 Z vjudge1 Ekoeko (COCI21_ekoeko) C++17
20 / 110
 8 ms 4188 KB 
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
 
 
int invcount(int *arr, int n){
    if (n < 2) return 0;
    int arr1[n / 2];
    for (int i = 0; i < n / 2; i++) arr1[i] = arr[i];
    int arr2[n - n / 2];
    for (int i = n / 2; i < n; i++) arr2[i - n / 2] = arr[i];
    int ans = invcount(arr1, n / 2) + invcount(arr2, n  - n / 2);
    int p1 = 0, p2 = 0;
    while (p1 + p2 < n){
        if (p2 == n - n / 2){
            arr[p1 + p2] = arr1[p1];
            p1++;
        } else if (p1 == n / 2){
            arr[p1 + p2] = arr2[p2];
            p2++;
        } else if (arr1[p1] < arr2[p2]){
            arr[p1 + p2] = arr1[p1];
            p1++;
        } else {
            arr[p1 + p2] = arr2[p2];
            ans += n / 2 - p1;
            p2++;
        }
    }
    return ans;
}
 
 
int otherend[200000], rightend[100000];
pair<int, int> pairarr[100000];
 
 
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n, cntr = 0, ans, closedcount = 0;
    char c;
    cin >> n;
    vector<vector<int>> appr;
    appr.resize(26);
    for (int i = 0; i < 2 * n; i++){
        cin >> c;
        appr[c - 'a'].push_back(i);
    }
    for (int i = 0; i < 26; i++){
        for (uint32_t j = 0; j < appr[i].size() / 2; j++){
            otherend[appr[i][j]] = appr[i][j + appr[i].size() / 2];
            otherend[appr[i][j + appr[i].size() / 2]] = appr[i][j];
            pairarr[cntr] = {appr[i][j], appr[i][j + appr[i].size() / 2]};
            cntr++;
        }
    }
    sort(pairarr, pairarr + n);
    for (int i = 0; i < n; i++) rightend[i] = pairarr[i].second;
    ans = invcount(rightend, n);
    for (int i = 0; i < 2 * n; i++){
        if (i < otherend[i]) ans += closedcount;
        else closedcount++;
    }
    cout << ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 1684 KB Output is correct
3 Correct 6 ms 3040 KB Output is correct
4 Incorrect 8 ms 4188 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 1684 KB Output is correct
3 Correct 6 ms 3040 KB Output is correct
4 Incorrect 8 ms 4188 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 1684 KB Output is correct
3 Correct 6 ms 3040 KB Output is correct
4 Incorrect 8 ms 4188 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 352 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 1684 KB Output is correct
3 Correct 6 ms 3040 KB Output is correct
4 Incorrect 8 ms 4188 KB Output isn't correct
5 Halted 0 ms 0 KB -