Submission #163829

#	Time	Username	Problem	Language	Result	Execution time	Memory
163829		Alexa2001	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	66 ms	7244 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int Nmax = 2e5 + 5;

int n;
int F[Nmax], S[Nmax], a[Nmax], cnt[Nmax], sum_cnt[Nmax];

void norm()
{
    int i;
    for(i=1; i<=n; ++i)
        if(a[i] > 0) ++sum_cnt[a[i]];
    
    for(i=1; i<=n; ++i)
        sum_cnt[i] += sum_cnt[i-1], cnt[i] = 0;

    for(i=1; i<=n; ++i)
        if(a[i] > 0)
        {
            ++cnt[a[i]];
            a[i] = sum_cnt[a[i] - 1] + cnt[a[i]];
            S[a[i]] = i;
        }

    for(i=1; i<=n; ++i) cnt[i] = 0;

    for(i=1; i<=n; ++i)
        if(a[i] < 0)
        {
            a[i] *= -1;
            ++cnt[a[i]];
            a[i] = sum_cnt[a[i] - 1] + cnt[a[i]];
            F[a[i]] = i;
        }
}

class AIB 
{
    int a[Nmax];
    int ub(int x) { return (x&(-x)); }

public:
    void clear()
    {
        memset(a, 0, sizeof(a));
    }

    int query(int x)
    {
        int ans = 0;
        for(; x <= n; x += ub(x)) ans += a[x];
        return ans;
    }
    void update(int x)
    {
        for(; x; x -= ub(x)) a[x] ++;
    }
    void update(int x, int y)
    {
        for(; x; x-=ub(x)) a[x] --;
        for(; y; y-=ub(y)) a[y] ++;
    }
} aib;

ll solve1()
{
    ll ans = 0;
    int i;

    aib.clear();

    for(i=1; i<=n; ++i)
        if(i == max(F[a[i]], S[a[i]]))
        {
            int curr = min(F[a[i]], S[a[i]]); 
            ans += 2 * aib.query(curr);
            aib.update(curr);
        }

    aib.clear();

    for(i=1; i<=n; ++i)
        if(i == max(F[a[i]], S[a[i]]))
        {
            int curr = min(F[a[i]], S[a[i]]);
            ans += aib.query(curr);
            aib.update(curr, i);
        }

    return ans;
}   

ll solve2()
{
    int i, ans = 0;
    for(i=1; i<=n; ++i)
        ans += (F[i] > S[i]);
    return ans;
}

ll count_swaps(vector<int> s) 
{
    n = s.size();
    int i;
    for(i=1; i<=n; ++i) a[i] = s[i-1];

    norm();
    
   // for(i=1; i<=n; ++i) cerr << a[i] << ' '; cerr << "#\n";

  //  cerr << solve1() << '\n';
  //  cerr << solve2() << '\n';

    return solve1() + solve2();
}

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