Submission #227765

#	Time	Username	Problem	Language	Result	Execution time	Memory
227765		Romario8	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	106 ms	20460 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a;i>=b;i--)
#define pb push_back
#define rl "\n"
#define x first
#define y second
using namespace std;
int BIT[200001];
ll sum(int i)
{
    ll res=0;
    while(i>0)
    {
        res+=BIT[i];
        i-=i&-i;
    }
    return res;
}
void update(int i,ll n,int val)
{
    while(i<=n)
    {
        BIT[i]+=val;
        i+=i&-i;
    }
}
long long count_swaps(vector<int> s)
{
    ll ans=0;
    ll n=s.size();
    vector<vector<ll>> pr(2*n+1);
    ll k=0;
    rep(i,0,n)
    {
        pr[s[i]+n/2].pb(i+1);
    }
	vector<pair<int,int>> u;
	rep(i,1,n+1)
	{
	    rep(j,0,pr[i+n/2].size())
	    {
            u.pb(make_pair(min(pr[i+n/2][j],pr[-i+n/2][j]),max(pr[i+n/2][j],pr[-i+n/2][j])));
            if(pr[i+n/2][j]<pr[-i+n/2][j])ans++;
	    }
	}
	sort(u.begin(),u.end());
	rep(i,0,u.size())
	{
        int l=u[i].x;
        int r=u[i].y;
        ans+=r-l-1-(sum(l)-sum(r));
        update(l+1,n,1);
        update(r,n,-1);
	}
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:4:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(ll i=a;i<b;i++)
shoes.cpp:43:10:
      rep(j,0,pr[i+n/2].size())
          ~~~~~~~~~~~~~~~~~~~~   
shoes.cpp:43:6: note: in expansion of macro 'rep'
      rep(j,0,pr[i+n/2].size())
      ^~~
shoes.cpp:4:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(ll i=a;i<b;i++)
shoes.cpp:50:6:
  rep(i,0,u.size())
      ~~~~~~~~~~~~               
shoes.cpp:50:2: note: in expansion of macro 'rep'
  rep(i,0,u.size())
  ^~~
shoes.cpp:35:8: warning: unused variable 'k' [-Wunused-variable]
     ll k=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