Submission #334214

#	Time	Username	Problem	Language	Result	Execution time	Memory
334214		bigDuck	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	1101 ms	136556 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount




int fw[100010];
deque<int> l[100010], r[100010];


void update(int i, int x){
    for(int j=(100000-i+1); j<=100000; j+=(j&(-j))){
        fw[j]+=x;
    }
}

int query(int i){
    int res=0;
    for(int j=(100000-i+1); j>0; j-=(j&(-j))){
        res+=fw[j];
    }
    return res;
}

bool v[100010];

long long count_swaps(std::vector<int> s) {



int n=s.size()/2;



for(int i=0; i<2*n; i++){
    if(s[i]<0){
        l[-s[i] ].pb(i+1);
    }
    else{
        r[s[i] ].pb(i+1);
    }
}

ll res=0;
int p=1;
for(int i=1; i<=n; i++){
    while(v[p]==true){p++;}
    v[p]=true;
    int c=s[p-1];
    p+=query(p);
    if(c<0){
        int j=r[-c].front();
        v[j]=true;
        update(j, 1);
        j+=query(j);
        l[-c].pop_front();
        r[-c].pop_front();
        res+=j-p-2;
    }
    else{
        int j=l[c].front();
        v[j]=true;
        update(j, 1);
        j+=query(j);
        l[c].pop_front();
        r[c].pop_front();
        res+=j-p-1;
    }
}

return res;
}

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