oj.uz

답안 #268732

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
268732 2020-08-16T22:35:36 Z Puddlestomps Arranging Shoes (IOI19_shoes) C++14
10 / 100
 54 ms 10104 KB 
#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;
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);
    //shoes.fill(queue<int>());
    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] != 0)
        {
            //Add to queue
            qlinks[qback[sn]] = i;
            qback[sn] = i;
        }
        else
        {
            //cout << "QFRONT: " << qfront[sn] << "\n";
            linked[qfront[sn]] = i;
            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]);
        //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

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3456 KB Output is correct
2 Correct 2 ms 3456 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3456 KB Output is correct
2 Correct 2 ms 3456 KB Output is correct
3 Correct 3 ms 3456 KB Output is correct
4 Correct 2 ms 3584 KB Output is correct
5 Correct 3 ms 3456 KB Output is correct
6 Correct 3 ms 3456 KB Output is correct
7 Incorrect 2 ms 3456 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3456 KB Output is correct
2 Correct 2 ms 3456 KB Output is correct
3 Correct 3 ms 3456 KB Output is correct
4 Correct 3 ms 3456 KB Output is correct
5 Correct 3 ms 3456 KB Output is correct
6 Correct 2 ms 3456 KB Output is correct
7 Correct 3 ms 3456 KB Output is correct
8 Correct 2 ms 3456 KB Output is correct
9 Incorrect 3 ms 3584 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3456 KB Output is correct
2 Correct 3 ms 3584 KB Output is correct
3 Correct 2 ms 3456 KB Output is correct
4 Correct 2 ms 3456 KB Output is correct
5 Runtime error 54 ms 10104 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3456 KB Output is correct
2 Correct 2 ms 3456 KB Output is correct
3 Correct 3 ms 3456 KB Output is correct
4 Correct 2 ms 3584 KB Output is correct
5 Correct 3 ms 3456 KB Output is correct
6 Correct 3 ms 3456 KB Output is correct
7 Incorrect 2 ms 3456 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3456 KB Output is correct
2 Correct 2 ms 3456 KB Output is correct
3 Correct 3 ms 3456 KB Output is correct
4 Correct 2 ms 3584 KB Output is correct
5 Correct 3 ms 3456 KB Output is correct
6 Correct 3 ms 3456 KB Output is correct
7 Incorrect 2 ms 3456 KB Output isn't correct
8 Halted 0 ms 0 KB -