Submission #268731

#	Time	Username	Problem	Language	Result	Execution time	Memory
268731		Puddlestomps	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	272 ms	187048 KiB

shoes

#include "bits/stdc++.h"

using namespace std;

constexpr int MAXN = 1 << 17;
array<int, MAXN * 2> segTree;
array<queue<int>, MAXN> shoes;
array<bool, MAXN> starts; // true if swapped
array<int, MAXN> linked;

//pos goes from 0
void put(int pos, int val)
{
    pos += MAXN;
    int diff = val - segTree[pos];
    while(pos > 0)
    {
        segTree[pos] += diff;
        pos = pos >> 1;
    }
}

//pos from 0, inclusive
int qry(int left, int right)
{
    int total = 0;
    left += MAXN;
    right += MAXN;
    while(left < right)
    {
        if((left & 1) == 1)
        {
            total += segTree[left];
            left++;
        }
        if((right & 1) == 0)
        {
            total += segTree[right];
            right--;
        }
        left = left >> 1;
        right = right >> 1;
    }

    if(left == right) total += segTree[left];

    return total;
}

long long count_swaps(vector<int> S)
{
    segTree.fill(0);
    starts.fill(false);
    shoes.fill(queue<int>());
    linked.fill(-1);

    long long total = 0;

    for(int i = 0; i < S.size(); i++)
    {
        int sn = abs(S[i]);

        if(shoes[sn].empty())
        {
            starts[i] = S[i] > 0;
            shoes[sn].push(i);
        }
        else if(S[shoes[sn].front()] + S[i] != 0)
        {
            starts[i] = S[i] > 0;
            shoes[sn].push(i);
        }
        else
        {
            //cout << "SHOES[SN]: " << shoes[sn].front() << "\n";
            linked[shoes[sn].front()] = i;
            total += i - shoes[sn].front();
            //cout << "ADD: " << (i - shoes[sn].front()) << "\n";
            if(!starts[shoes[sn].front()])
            {
                //cout << "NOT STARTS\n";
                total--;
            }

            shoes[sn].pop();
        }
        
        put(i, S[i] < 0 ? 1 : -1);
    }

    //cout << "TOTAL PRE PROCESS: " << total << "\n";

    for(int ind = 0; ind < S.size(); ind++)
    {
        if(segTree[MAXN + ind] == 0) continue;

        int helps = qry(ind, linked[ind]);
        //cout << "HELPS from " << ind << " to " << linked[ind] << ": " << helps << "\n";
        total -= helps;

        put(ind, 0);
        put(linked[ind], 0);
    }
    
    return total;
}

/*
int main()
{
    int num;
    vector<int> vals;

    cin >> num;
    vals.resize(num);

    for(int i = 0; i < num; i++) cin >> vals[i];
    
    cout << count_swaps(vals) << "\n";

    
}*/

Compilation message (stderr)

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

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