Submission #1144939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144939		MunkhturErdenebat	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	0 ms	328 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;

long long count_swaps(vector<int> s) {
    int n = s.size();
    unordered_map<int, vector<int>> vas;
    unordered_map<int, int> mee;
    unordered_map<int, int> visited;
    vector<int> vii;
    for (int i = 0; i < n; i++) {
        vas[s[i]].push_back(i);
    }

    long long sum = 0;
    
    for (int i = 0; i < n; i++) {
        if (visited[i] == 0) {
            int l = 0, r = vii.size() - 1, g;
            while (l < r) {
                int m = (l + r - 1) / 2;
                if (vii[m] > i) {
                    r = m;
                } else {
                    l = m + 1;
                }
            }
            g = l;

            l = 0, r = vii.size() - 1;
            while (l < r) {
                int m = (l + r + 1) / 2;
                if (vii[m] > vas[-s[i]][mee[-s[i]]]) {
                    r = m - 1;
                } else {
                    l = m;
                }
            }
            vii.push_back(vas[-s[i]][mee[-s[i]]]);
            sort(vii.begin(), vii.end());
            if(l<g){
                sum += vas[-s[i]][mee[-s[i]]]-i;
            }
            else{
                sum += vas[-s[i]][mee[-s[i]]]-i-l + g -1;
            }
            if(s[i]>0){
                sum++;
            }
            visited[vas[-s[i]][mee[-s[i]]]] = 1;
            mee[s[i]]++;
            mee[-s[i]]++;
        }
    }

    return sum;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15