Submission #832687

#	Time	Username	Problem	Language	Result	Execution time	Memory
832687		Marco_Escandon	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	291 ms	413420 KiB

shoes

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct st{
    vector<ll> asd;
    void update(ll a, ll b)
    {
        for(a; a<asd.size(); a+=(a&(-a)))
        {
            asd[a]+=b;
        }
    }
    ll query(ll a)
    {
        ll cont=0;
        for(a; a>0; a-=(a&(-a)))
        {
            cont+=asd[a];
        }
        return cont;
    }
    st(ll n)
    {
        asd.resize(2*n);
    }
};
#define op -s[i]+n
long long count_swaps(std::vector<int> s) {
    ll n= s.size();
    vector<ll> inv(n,0);
    vector<queue<ll>> asd(n*3);
    for(int i=0; i<n; i++)
        asd[s[i]+n].push(i);
    ll cont=1;
    for(int i=0; i<n; i++)
    {
        if(s[i]!=0)
        {
            if(s[i]<0)
            {
                inv[i]=cont;
                asd[s[i]+n].pop();
                cont++;
                inv[asd[op].front()]=cont;
                cont++;
            }
            else
            {
                inv[i]=cont+1;
                asd[s[i]+n].pop();
                inv[asd[op].front()]=cont;
                cont+=2;
            }
            s[asd[op].front()]=0;
            asd[op].pop();
            s[i]=0;
        }
    }
    st asdf(n);
    cont=0;
    /*for(auto i:inv)
    {
        cout<<i<<" ";
    }
    cout<<"\n";*/
    for(int i=n-1; i>-1; i--)
    {
        cont+=asdf.query(inv[i]);
        asdf.update(inv[i],1);
    }
    return cont;
}

Compilation message (stderr)

shoes.cpp: In member function 'void st::update(ll, ll)':
shoes.cpp:8:13: warning: statement has no effect [-Wunused-value]
    8 |         for(a; a<asd.size(); a+=(a&(-a)))
      |             ^
shoes.cpp:8:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |         for(a; a<asd.size(); a+=(a&(-a)))
      |                ~^~~~~~~~~~~
shoes.cpp: In member function 'll st::query(ll)':
shoes.cpp:16:13: warning: statement has no effect [-Wunused-value]
   16 |         for(a; a>0; a-=(a&(-a)))
      |             ^

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