Submission #863674

#	Time	Username	Problem	Language	Result	Execution time	Memory
863674		AliHasanli	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	17 ms	8656 KiB

shoes

#include<iostream> 
#include<vector>
#include<map>
#include<set>
using namespace std;
vector<int>sgtree(262144);
map<int,set<int>>mp;
int indd(int ind)
{
    int ans=131072+ind;
    return ans;
}
void update(int ind)
{
    if(ind==1){sgtree[ind]+=1;return;}
    sgtree[ind]+=1;
    update(ind/2);
}
int query(int L,int R,int l,int r,int index)
{
    if(l>r) return 0;
    if(r<L || R<l)return 0;
    if(l==r)return sgtree[index];
    if(L<=l && r<=R) return sgtree[index];
    return query(L,R,l,(l+r)/2,index*2)+query(L,R,(r+l)/2+1,r,index*2+1);
}
long long count_swaps(vector<int> s)
{
    long long ans=0;
    int a[s.size()]={0};
    for(int i=0;i<s.size();i++)
        sgtree[131072+i]=a[i];
    for(int i=0;i<s.size();i++)
        mp[s[i]].insert(i);
    for(int i=0;i<s.size();i++)
    {
        if(a[i]==0)
        {
        a[i]=1;
        mp[s[i]].erase(0);
        mp[-s[i]].erase(0);
        int nextind=0;
        update(indd(i));
        for(int j:mp[-s[i]])
        {
            nextind=j;
            break;
        }
        update(indd(nextind));
        a[nextind]=1;
        if(i+1==nextind)
            if(s[i]>s[nextind])ans++;
        if(i+1<nextind)
        {
            ans+=(nextind-i-1-query(i+2,nextind,1,131072,1));
            if(s[i]>s[nextind])ans++;
        }
        }
    }
    return ans;
}

Compilation message (stderr)

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

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