Submission #980597

#	Time	Username	Problem	Language	Result	Execution time	Memory
980597		TitanicXDzz	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	49 ms	16832 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> v[200010];
int co[200010];
int dp[200010];
int visited[200010];
int n;
void update(int idx,long long val){
 while(idx<=n){
    dp[idx]+=val;
    idx+=(idx & -idx);
 }
}
long long read(long long idx){
 long long sumi=0;
 while(idx>=1){
        sumi+=dp[idx];
        idx-=(idx& -idx);
 }
 return sumi;
}
long long count_swaps(vector<int> s) {
    long long ans=0;
    for(auto x:s){
        n++;
        if(s[n-1]<0)
            s[n-1]=100000-s[n-1];
        v[s[n-1]].push_back(n);
    }
    for(int i=1;i<=n;i++){
        update(i,1);
    }
    for(int i=1;i<=n;i++){
        if(visited[i]==1)
            continue;
        long long x=s[i-1];
        if(x>=100001)
            x-=100000;
        else
            x+=100000;
        int j=v[x][co[x]];
        visited[i]=1;
        visited[j]=1;
        co[x]++;
        co[s[i-1]]++;
        ans+=read(j)-1;
        update(i,-1);
        update(j,-1);
        if(x<s[i-1]){
            ans-=1;
        }
    }
    return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:25:14: warning: unused variable 'x' [-Wunused-variable]
   25 |     for(auto x:s){
      |              ^

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