oj.uz

Submission #268734

# Submission time Handle Problem Language Result Execution time Memory
268734 2020-08-16T22:59:03 Z Puddlestomps Arranging Shoes (IOI19_shoes) C++14
25 / 100
 53 ms 9728 KB 
#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;
        }
        else if(S[qfront[sn]] == S[i])
        {
            //Add to queue
            //cout << "QUEUE EXTENDED\n";
            qlinks[qback[sn]] = i;
            qback[sn] = i;
        }
        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, 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]);
        //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

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:102:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int ind = 0; ind < S.size(); ind++)
      |                      ~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6784 KB Output is correct
2 Correct 5 ms 6784 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6784 KB Output is correct
2 Correct 5 ms 6784 KB Output is correct
3 Correct 5 ms 6784 KB Output is correct
4 Correct 5 ms 6656 KB Output is correct
5 Correct 5 ms 6784 KB Output is correct
6 Correct 5 ms 6656 KB Output is correct
7 Incorrect 5 ms 6784 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6784 KB Output is correct
2 Correct 5 ms 6784 KB Output is correct
3 Correct 6 ms 6656 KB Output is correct
4 Correct 5 ms 6656 KB Output is correct
5 Correct 5 ms 6656 KB Output is correct
6 Correct 5 ms 6656 KB Output is correct
7 Correct 5 ms 6656 KB Output is correct
8 Correct 5 ms 6784 KB Output is correct
9 Incorrect 6 ms 6656 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6656 KB Output is correct
2 Correct 6 ms 6784 KB Output is correct
3 Correct 5 ms 6656 KB Output is correct
4 Correct 6 ms 6656 KB Output is correct
5 Correct 49 ms 8312 KB Output is correct
6 Correct 51 ms 9592 KB Output is correct
7 Correct 52 ms 9720 KB Output is correct
8 Correct 48 ms 9728 KB Output is correct
9 Correct 49 ms 9584 KB Output is correct
10 Correct 53 ms 9592 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6784 KB Output is correct
2 Correct 5 ms 6784 KB Output is correct
3 Correct 5 ms 6784 KB Output is correct
4 Correct 5 ms 6656 KB Output is correct
5 Correct 5 ms 6784 KB Output is correct
6 Correct 5 ms 6656 KB Output is correct
7 Incorrect 5 ms 6784 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6784 KB Output is correct
2 Correct 5 ms 6784 KB Output is correct
3 Correct 5 ms 6784 KB Output is correct
4 Correct 5 ms 6656 KB Output is correct
5 Correct 5 ms 6784 KB Output is correct
6 Correct 5 ms 6656 KB Output is correct
7 Incorrect 5 ms 6784 KB Output isn't correct
8 Halted 0 ms 0 KB -