Submission #269777

#	Time	Username	Problem	Language	Result	Execution time	Memory
269777		Puddlestomps	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	64 ms	9732 KiB

shoes

#include "bits/stdc++.h"

using namespace std;

constexpr int MAXN = 1 << 18;
array<int, MAXN * 2> segTree;
array<bool, MAXN> starts; // true if swapped
array<int, MAXN> linked;
//Queue for same shoes to get matched
array<int, MAXN> qfront, qlinks, qback; //Takes sn and gives first position of that shoe size in q, links between positions for what next should be after qfront is used, takes sn and gives position of last thing in q

//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);
    linked.fill(-1);
    qfront.fill(-1);
    qlinks.fill(-1);
    qback.fill(-1);

    long long total = 0;

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

        starts[i] = S[i] > 0;
        
        if(qfront[sn] == -1)
        {
            //Create queue
            qfront[sn] = i;
            qback[sn] = i;
            put(i, 1);
        }
        else if(S[qfront[sn]] == S[i])
        {
            //Add to queue
            //cout << "QUEUE EXTENDED\n";
            qlinks[qback[sn]] = i;
            qback[sn] = i;
            put(i, 1);
        }
        else
        {
            //cout << "QFRONT: " << qfront[sn] << "\n";
            linked[qfront[sn]] = i;
            //if(qfront[sn] < 100) cout << "LINKED at " << qfront[sn] << ": " << linked[qfront[sn]] << "\n";
            total += i - qfront[sn];
            //cout << "ADD: " << (i - qfront[sn]) << "\n";
            if(!starts[qfront[sn]])
            {
                //cout << "NOT STARTS\n";
                total--;
            }

            qfront[sn] = qlinks[qfront[sn]];
            put(i, -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]);
        //if(ind < 100) cout << "HELPS from " << ind << " to " << linked[ind] << ": " << helps << "\n";
        total -= helps;

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

/*
int main()
{
    //ifstream in("shoes.05.inp");
    
    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:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = 0; i < S.size(); i++)
      |                    ~~^~~~~~~~~~
shoes.cpp:103:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int ind = 0; ind < S.size(); ind++)
      |                      ~~~~^~~~~~~~~~

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