Submission #761104

#	Time	Username	Problem	Language	Result	Execution time	Memory
761104		raysh07	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	73 ms	72568 KiB

shoes

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

const int N = 2e5 + 69;
int f[N];
int m;

void add(int x, int v){
    for (int i = x; i <= m; i += i & (-i)) f[i] += v;
}

int sum(int x){
    int ret = 0;
    for (int i = x; i; i -= i & (-i)) ret += f[i];
    return ret;
}

long long count_swaps(vector<int> s) {
    long long ans = 0;
    
    int n = s.size() / 2;
    m = 2 * n;
    vector <int> match(m + 1, -1);
    deque <int> store[n + 1];
    
    for (int i = 0; i < m; i++){
        int x = abs(s[i]);
        int sgn = s[i] / x;
        
        if (sgn == 1){
            if (store[x].size() > 0 && store[x][0] < 0){
                match[-store[x][0]] = i + 1;
                match[i + 1] = -store[x][0];
                store[x].pop_front();
            } else {
                store[x].push_back(i + 1);
            }
        } else {
            if (store[x].size() > 0 && store[x][0] > 0){
                match[store[x][0]] = i + 1;
                match[i + 1] = store[x][0];
                store[x].pop_front();
            } else {
                store[x].push_back(-i - 1);
            }
        }
    }
    
    for (int i = 1; i <= 2 * n; i++) add(i, 1);
    
    for (int i = 1; i <= 2 * n; i++){
        if (match[i] < i) continue;
        
        int holy;
        
        holy = sum(match[i] - 1) - sum(i);
       // cout << holy << " ";
        if (s[match[i] - 1] < 0) holy++;
       // cout << holy << "\n";
        ans += holy;
        add(match[i], -1);
    }
    
    return ans;
}

// int main(){
//     int n; cin >> n;
//     vector <int> a(n);
//     for (auto &x : a) cin >> x;
    
//     cout << count_swaps(a) << "\n";
//   return 0; 
// }

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