Submission #769187

#	Time	Username	Problem	Language	Result	Execution time	Memory
769187		Andrey	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	166 ms	45380 KiB

shoes

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

long long haha[200001][19];

void add(long long a) {
    for(long long i = 0; i < 19; i++) {
        a-=(a%(1 << i));
        haha[a][i]++;
    }
}

long long calc(long long a, long long b) {
    long long j = 0;
    long long ans = 0;
    while(a < b) {
        j = 0;
        while(a%(1 << j) == 0 && a+(1 << j) <= b) {
            j++;
        }
        j--;
        ans+=haha[a][j];
        a+=(1 << j);
    }
    return ans+haha[b][0];
}

long long count_swaps(vector<int> s) {
    const long long y = 100000;
    long long n = s.size()/2,p,a,ans = 0;
    for(long long i = 0; i < 200001; i++) {
        for(long long j = 0; j < 19; j++) {
            haha[i][j] = 0;
        }
    }
    vector<long long> bruh(2*n);
    vector<vector<long long>> yeah(200001);
    for(long long i = 0; i < 2*n; i++) {
        bruh[i] = s[i];
    }
    for(long long i = 2*n-1; i >= 0; i--) {
        yeah[bruh[i]+y].push_back(i);
    }
    for(long long i = 0; i < 2*n; i++) {
        if(bruh[i] != -INT_MAX) {
            while(yeah[-bruh[i]+y][yeah[-bruh[i]+y].size()-1] < i) {
                yeah[-bruh[i]+y].pop_back();
            }
            if(bruh[i] < 0) {
                p = yeah[-bruh[i]+y][yeah[-bruh[i]+y].size()-1];
                a = 0;
            }
            else {
                p = yeah[-bruh[i]+y][yeah[-bruh[i]+y].size()-1];
                a = 1;
            }
            yeah[-bruh[i]+y].pop_back();
            bruh[p] = -INT_MAX;
            ans += p-i-1-calc(i,p-1)+a;
            add(p);
            add(i);
        }
    }
    return ans;
}

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