Submission #1041033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041033		idas	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	34 ms	19036 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back

using namespace std;
typedef long long ll;
typedef vector<ll> vi;

const int N=2e5+10;
int n, cn[N];
vi max_pos[N][2];

void add_cn(int p)
{
    p++;
    for(int i=p; i<N; i+=i&(-i)) cn[i]++;
}

int get_cn(int p)
{
    p++;
    int ret=0;
    for(int i=p; i>0; i-=i&(-i)) ret+=cn[i];
    return ret;
}

int range(int i, int j)
{
    if(i>j) return 0;
    return get_cn(j)-get_cn(i-1);
}

long long count_swaps(vector<int> s) {
    n=s.size();
    FOR(i, 0, n)
    {
        int x=abs(s[i]), y=s[i]<0?0:1;
        max_pos[x][y].pb(i);
    }

    ll ans=0;
    int neg=0;
    vector<bool> used(n, false);
    for(int i=n-1; i>=0; i--){
//        cout << i << ": ";
//        FOR(i, 0, n) cout << used[i];
//        cout << endl;
        while(i>=0 && used[i]){
            i--;
            neg--;
        }
        if(i<0) break;
        if(s[i]<0){
            assert(!max_pos[-s[i]][1].empty());
            int true_i=i-neg, j=max_pos[-s[i]][1].back();
            max_pos[-s[i]][1].pop_back();
            int true_j=j-(neg-range(j,i-1));
            ans+=true_i-true_j;
            used[j]=true;
            add_cn(j);
        }
        else{
            assert(!max_pos[s[i]][0].empty());
            int true_i=i-neg, j=max_pos[s[i]][0].back();
            max_pos[s[i]][0].pop_back();
            int true_j=j-(neg-range(j,i-1));
            ans+=true_i-true_j-1;
            used[j]=true;
            add_cn(j);
        }
        neg++;
    }

    return ans;
}

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