oj.uz

Submission #143875

# Submission time Handle Problem Language Result Execution time Memory
143875 2019-08-15T11:50:27 Z stoyan_malinin Arranging Shoes (IOI19_shoes) C++14
10 / 100
 1000 ms 270516 KB 
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>

using namespace std;

const int MAXN = 2e5 + 5;

struct fenwickTree
{
    int tree[MAXN];

    fenwickTree()
    {
        memset(this->tree, 0, sizeof(this->tree));
    }

    void update(int index, int value)
    {
        index++;
        while(index<MAXN)
        {
            this->tree[index] += value;
            index += index&(-index);
        }
    }

    int query(int index)
    {
        int sum = 0;

        index++;
        while(index>0)
        {
            sum += this->tree[index];
            index -= index&(-index);
        }

        return sum;
    }
};

fenwickTree *T = new fenwickTree();

queue <int> leftShoes[MAXN], rightShoes[MAXN];
int bestLeft[MAXN], bestRight[MAXN];

int moveElement(int i, int j, vector <int> &s)
{
    int cnt = 0;
    while(j>i)
    {
        cnt++;

        swap(s[j-1], s[j]);
        j--;
    }

    return cnt;
}

int calcValue(int num, int index)
{
    int sum = (bestLeft[num] - index) + (bestRight[num] - (index+1));
    if(bestLeft[num]>bestRight[num]) sum++;

    return sum;
}

long long count_swaps(vector <int> s)
{
    for(int i = 0;i<s.size();i++)
    {
        if(s[i]<0) leftShoes[ -s[i] ].push(i);
        else rightShoes[ s[i] ].push(i);
    }

    int answer = 0;
    for(int index = 0;index<s.size();index+=2)
    {
        //memset(bestLeft, -1, sizeof(bestLeft));

        /*
        for(int i = s.size()-1;i>=index;i--)
        {
            if(s[i]<0) bestLeft[ -s[i] ] = i;
            else bestRight[ s[i] ] = i;
        }
        */


        int bestIndex = -1;


        bestIndex = abs(s[index]);
        bestLeft[bestIndex] = leftShoes[bestIndex].front() - T->query(leftShoes[bestIndex].front());leftShoes[bestIndex].pop();
        bestRight[bestIndex] = rightShoes[bestIndex].front() - T->query(rightShoes[bestIndex].front());rightShoes[bestIndex].pop();

        T->update(bestLeft[bestIndex], 1);
        T->update(bestRight[bestIndex], 1);

        //cout << "   " << bestIndex << '\n';

        answer += calcValue(bestIndex, 0);
    }

    //for(int i = 0;i<s.size();i++) cout << s[i] << " ";
    //cout << '\n';

    return answer;
}

Compilation message

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<s.size();i++)
                   ~^~~~~~~~~
shoes.cpp:80:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int index = 0;index<s.size();index+=2)
                       ~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 270416 KB Output is correct
2 Correct 270 ms 270456 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 270416 KB Output is correct
2 Correct 270 ms 270456 KB Output is correct
3 Correct 285 ms 270504 KB Output is correct
4 Correct 325 ms 270488 KB Output is correct
5 Correct 273 ms 270400 KB Output is correct
6 Correct 281 ms 270328 KB Output is correct
7 Execution timed out 1037 ms 270336 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 270416 KB Output is correct
2 Correct 270 ms 270456 KB Output is correct
3 Correct 271 ms 270436 KB Output is correct
4 Correct 275 ms 270328 KB Output is correct
5 Correct 279 ms 270376 KB Output is correct
6 Correct 274 ms 270444 KB Output is correct
7 Correct 271 ms 270428 KB Output is correct
8 Correct 276 ms 270324 KB Output is correct
9 Correct 312 ms 270344 KB Output is correct
10 Correct 277 ms 270352 KB Output is correct
11 Correct 282 ms 270356 KB Output is correct
12 Correct 266 ms 270396 KB Output is correct
13 Execution timed out 1075 ms 270516 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 270428 KB Output is correct
2 Execution timed out 1079 ms 270404 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 270416 KB Output is correct
2 Correct 270 ms 270456 KB Output is correct
3 Correct 285 ms 270504 KB Output is correct
4 Correct 325 ms 270488 KB Output is correct
5 Correct 273 ms 270400 KB Output is correct
6 Correct 281 ms 270328 KB Output is correct
7 Execution timed out 1037 ms 270336 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 270416 KB Output is correct
2 Correct 270 ms 270456 KB Output is correct
3 Correct 285 ms 270504 KB Output is correct
4 Correct 325 ms 270488 KB Output is correct
5 Correct 273 ms 270400 KB Output is correct
6 Correct 281 ms 270328 KB Output is correct
7 Execution timed out 1037 ms 270336 KB Time limit exceeded
8 Halted 0 ms 0 KB -