Submission #1003736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003736		vjudge1	Ekoeko (COCI21_ekoeko)	C++17	20 / 110	8 ms	4188 KiB

Main

#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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 40