Submission #437475

#	Time	Username	Problem	Language	Result	Execution time	Memory
437475		robertbarbu27	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	93 ms	12012 KiB

shoes

#include <bits/stdc++.h>
#define nl '\n'
#define pb push_back
#define ll long long
#define VMAX 100001
#define NMAX 35005
#define INF 10000000000000000

using namespace std;
vector<int> poz[200005];
int v[200005],ant[200005],N;
int aib[200005];
void update(int poz,int val)
{
    for(int i=poz;i<=2*N;i+=(i&(-i)))
    {
        aib[i]+=val;
    }
}
int query(int poz)
{
    int ans=0;
    for(int i=poz;i>0;i-=i&(-i))
    {
        ans+=aib[i];
    }
    return ans;
}
long long count_swaps(std::vector<int> s)
{
    N=s.size()/2;
    //cout<<N<<" ";
    for(int i=0;i<2*N;i++)
    {
        poz[abs(s[i])].pb(i+1);
        v[i+1]=s[i];
    }
        //cout<<N<<" ";
    long long ans=0;
    for(int i=1;i<=N;i++)
    {
        vector<int> pl,mn;
        for(int j=0;j<poz[i].size();j++)
        {
            if(v[poz[i][j]]>0)
            {
                pl.pb(poz[i][j]);
            }
            else mn.pb(poz[i][j]);
        }
        for(int j=0;j<mn.size();j++)
        {
            if(mn[j]>pl[j])
            {
                swap(mn[j],pl[j]);
                swap(v[mn[j]],v[pl[j]]);
                ans++;

            }
            ant[pl[j]]=mn[j];
        }
    }
    for(int i=2*N;i>=1;i--)
    {
        if(v[i]>0)
        {
            int x=i-query(i);
            int y=ant[i]-query(ant[i]);
            ans+=x-y-1;
            //cout<<ant[i]<<" ";
            update(ant[i],1);
        }
    }

    return ans;


}
/*
int main() {
	int n;
	assert(1 == scanf("%d", &n));
	vector<int> S(2 * n);
	for (int i = 0; i < 2 * n; i++)
		assert(1 == scanf("%d", &S[i]));
	fclose(stdin);

	long long result = count_swaps(S);

	printf("%lld\n", result);
	fclose(stdout);
	return 0;
}
*/

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for(int j=0;j<poz[i].size();j++)
      |                     ~^~~~~~~~~~~~~~
shoes.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int j=0;j<mn.size();j++)
      |                     ~^~~~~~~~~~

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