Submission #1188759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188759		orgiloogii	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	126 ms	21320 KiB

shoes

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#define ll long long
using namespace std;

vector <ll> sum, a;
void build(int id, int l, int r){
    if(l == r){
        sum[id] = 1;
        return;
    }
    int m = (l + r) / 2, x = id * 2 + 1, y = x + 1;
    build(x, l, m);
    build(y, m + 1, r);
    sum[id] = sum[x] + sum[y];
}
void update(int id, int l, int r, int i){
    if(l == r){
        sum[id] = 0;
        return;
    }
    int m = (l + r) / 2, x = 2 * id + 1, y = x + 1;
    if(i <= m){
        update(x, l, m, i);
    }
    else{
        update(y, m + 1, r, i);
    }
    sum[id] = sum[x] + sum[y];
}

ll query(int id, int l, int r, int L, int R){
    if(L == l && r == R){
        return sum[id];
    }
    int m = (l + r) / 2, x = id * 2 + 1, y = x + 1;
    if(R <= m) return query(x, l, m, L, R);
    if(L >= m + 1) return query(y, m + 1, r, L, R);
    return query(x, l, m, L, m) + query(y, m + 1, r, m + 1, R);
}

long long count_swaps(vector<int> s) {
    int n = s.size();
    a.resize(n);
    sum.resize(4 * n, 0);
    for (int i = 0;i < n;i++) a[i] = s[i];
    vector <vector <int>> adj(n / 2 + 1), adj1(n / 2 + 1); //adj = eyreg, adj1 = surug;
    for (int i = 0;i < n;i++) {
        if (s[i] < 0) {
            adj1[-s[i]].push_back(i);
        }
        else {
            adj[s[i]].push_back(i);
        }
    }
    int id[n / 2 + 1] = {0};
    // for (int i = 0;i < n;i++) {
    //     if (s[i] < 0) {
    //         adj1[-s[i]].push_back(i);
    //     }
    //     else {
    //         adj[s[i]].push_back(i);
    //     }
    // }
    // for (int i = 0;i < adj.size();i++) {
    //     cout << i << ": ";
    //     for (auto x : adj[i]) {
    //         cout << x << " ";
    //     }
    //     cout << endl;
    // }
    // for (int i = 0;i < adj1.size();i++) {
    //     cout << -i << ": ";
    //     for (auto x : adj1[i]) {
    //         cout << x << " ";
    //     }
    //     cout << endl;
    // }
    bool vis[n] = {0};
    build(0, 0, n - 1);
    ll res = 0;
    for (int i = 0;i < n;i++) {
        if (!vis[i]) {
            if (s[i] < 0) {
                if (adj1[-s[i]][id[-s[i]]] + 1 == adj[-s[i]][id[-s[i]]]) {
                    vis[i] = true;
                    vis[i + 1] = true;
                    id[-s[i]]++;
                    continue;
                }
                res += query(0, 0, n - 1, adj1[-s[i]][id[-s[i]]] + 1, adj[-s[i]][id[-s[i]]] - 1);
                update(0, 0, n - 1, adj1[-s[i]][id[-s[i]]]);
                update(0, 0, n - 1, adj[-s[i]][id[-s[i]]]);
                vis[adj1[-s[i]][id[-s[i]]]] = true;
                vis[adj[-s[i]][id[-s[i]]]] = true;
                id[-s[i]]++;
            }
            else {
                if (adj1[s[i]][id[s[i]]] - 1 == adj[s[i]][id[s[i]]]) {
                    vis[i] = true;
                    vis[i + 1] = true;
                    id[s[i]]++;
                    res++;
                    continue;
                }
                res += query(0, 0, n - 1, adj[s[i]][id[s[i]]] + 1, adj1[s[i]][id[s[i]]] - 1) + 1;
                update(0, 0, n - 1, adj1[s[i]][id[s[i]]]);
                update(0, 0, n - 1, adj[s[i]][id[s[i]]]);
                vis[adj1[s[i]][id[s[i]]]] = true;
                vis[adj[s[i]][id[s[i]]]] = true;
                id[s[i]]++;
            }
        }
    }
    return res;
}
// int main() {
//     cout << count_swaps({-2, 2, 2, -2, -2, 2});
// }

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