Submission #1045584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045584		boyliguanhan	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	65 ms	73948 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
queue<int> otherpos[100100];
int T[200100];
void Add(int x){
    while(x<200100)
        T[x]++,x+=x&-x;
}
int Qry(int x){
    int ans=0;
    while(x)
        ans+=T[x],x-=x&-x;
    return ans;
}
long long calc(vector<int>v){
    long long ans=0;
    int K=0;
    for(auto i:v) {
        Add(i+1);
        ans+=K++-Qry(i);
    }
    return ans;
}
long long count_swaps(std::vector<int> s) {
    long long ans=0;
    int n=s.size()>>1;
    vector<int>sup;
    int CC=0;
    for(int i=0;i<n*2;i++) if(s[i]<0)
        otherpos[-s[i]].push(i);
    CC=0;
	vector<pair<int,int>> thgs;
    for(int i=0;i<n*2;i++) if(s[i]>0) {
        int x=otherpos[s[i]].front();
		thgs.push_back({x,i});
        otherpos[s[i]].pop();
    }
	for(auto&[i,j]:thgs)
		if(i>j)
			ans++,swap(i,j);
	sort(thgs.begin(),thgs.end());
	for(auto[i,j]:thgs)
		sup.push_back(i),
		sup.push_back(j);
    return ans+calc(sup);
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:29:9: warning: variable 'CC' set but not used [-Wunused-but-set-variable]
   29 |     int CC=0;
      |         ^~

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