Submission #739262

#	Time	Username	Problem	Language	Result	Execution time	Memory
739262		nicolaev	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	1 ms	212 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
 
using namespace std;
#define mod                1000000007
#define ll                 int
#define all(v)             v.begin(), v.end()
#define fr(n)              for(ll i=0;i<n;++i)
#define ctz(x)             __builtin_ctzll(x)
#define clz(x)             __builtin_clzll(x)
#define pcount(x)          __builtin_popcountll(x)
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
// #define cin fin
// #define cout fout
// ifstream fin
// ofstream fout
//const ll maxn = 3e5 + 5;
//int f[maxn],nf[maxn],inv[maxn];
//const int M=998244353;
//void init(){
//inv[1]=1; for (int i=2;i<maxn;i++) inv[i]=M-1ll*(M/i)*inv[M%i]%M;
//f[0]=nf[0]=1; for (int i=1;i<maxn;i++) f[i]=1ll*f[i-1]*i%M,nf[i]=1ll*nf[i-1]*inv[i]%M;
//}
//int C(int x,int y){return 1ll*f[x]*nf[y]%M*nf[x-y]%M;}

long long count_swaps(vector<ll> s){
    ll n=s.size();
    vector< set<ll> > v(n+4);
    
    for(ll i=0; i<n; i++){
        if(s[i]<0){
            v[abs(s[i])+n/2].insert(i);
        }
        else v[s[i]].insert(i);
    }
    long long ans=0;
    for(ll i=0; i<n; i++){
        
        if(s[i]<0){
            if(v[abs(s[i])+n/2].empty()) continue;
            v[abs(s[i])+n/2].erase(i);
            set<ll> ::iterator it=v[abs(s[i])].begin();
            ans+=*it-i+1;
            v[abs(s[i])].erase(it);
        }
        else{
            if(v[s[i]].empty()) continue;
            v[s[i]].erase(i);
            set<ll> ::iterator it=v[n/2+s[i]].begin();
            ans+=*it-i;
            v[n/2+s[i]].erase(it);
        }
    }
    return ans;
    
}

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