Submission #1263998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263998		alosza	Arranging Shoes (IOI19_shoes)	C++20	Compilation error	0 ms	0 KiB

shoes

struct vec_queue
{
    vector<int> q;
    int c = 0;

    void push(int i)
    {
        q.push_back(i);
    }

    void pop()
    {
        c++;
    }

    int front()
    {
        return q[c];
    }
};

vector<int> tree;
int len=0;

void update(int v,int currStart,int currEnd,int lookStart,int lookEnd){
    if (currStart>=lookStart && currEnd<=lookEnd){
        tree[v]++;
        return;
    }

    if (currStart>lookEnd || currEnd<lookStart) return;

    int mid=(currStart+currEnd)/2;
    update(2*v,currStart,mid,lookStart,lookEnd);
    update(2*v+1,mid+1,currEnd,lookStart,lookEnd);
}

int get(int pos){
    pos+=len;
    int ans=tree[pos];

    while (pos>1){
        pos/=2;
        ans+=tree[pos];
    }
    return ans;
}

int64_t count_swaps(vector<int> S){
    tree.clear();
    int n=S.size();

    for (int i=1;i<=21;i++){
        int p=(1<<i);
        if (p>=n){
            len=p;
            break;
        }
    }

    tree.resize(2*len);

    vector<bool> skip(n);
    iota(tree.begin()+len+1,tree.end(),1);
    vector<pair<vec_queue,vec_queue>> pqs(n+1);

    for (int i=0;i<n;i++){
        if (S[i]>0){
            pqs[S[i]].first.push(i);
        } else {
            pqs[S[i]*-1].second.push(i);
        }
    }

    int64_t swaps=0;

    for (int i=0;i<n;i++){
        if (skip[i]) continue;

        int now=get(i);
        int next;

        if (S[i]>0){
            //szukam w ujemnych na .second
            next=pqs[S[i]].second.front();
            pqs[S[i]].second.pop();

            pqs[S[i]].first.pop(); //usuwamy now
        } else {
            //szukam w dodatnich na .first
            next=pqs[S[i]*-1].first.front();
            pqs[S[i]*-1].first.pop();

            pqs[S[i]*-1].second.pop();//usuwamy now
        }

        update(1,0,len-1,0,next-1);

        skip[i]=true;
        skip[next]=true;

        next=get(next);

        swaps+=next-now-1;

        if (S[i]>0) swaps++;
    }
    return swaps;
}

Compilation message (stderr)

shoes.cpp:3:5: error: 'vector' does not name a type
    3 |     vector<int> q;
      |     ^~~~~~
shoes.cpp: In member function 'void vec_queue::push(int)':
shoes.cpp:8:9: error: 'q' was not declared in this scope
    8 |         q.push_back(i);
      |         ^
shoes.cpp: In member function 'int vec_queue::front()':
shoes.cpp:18:16: error: 'q' was not declared in this scope
   18 |         return q[c];
      |                ^
shoes.cpp: At global scope:
shoes.cpp:22:1: error: 'vector' does not name a type
   22 | vector<int> tree;
      | ^~~~~~
shoes.cpp: In function 'void update(int, int, int, int, int)':
shoes.cpp:27:9: error: 'tree' was not declared in this scope
   27 |         tree[v]++;
      |         ^~~~
shoes.cpp: In function 'int get(int)':
shoes.cpp:40:13: error: 'tree' was not declared in this scope
   40 |     int ans=tree[pos];
      |             ^~~~
shoes.cpp: At global scope:
shoes.cpp:49:1: error: 'int64_t' does not name a type
   49 | int64_t count_swaps(vector<int> S){
      | ^~~~~~~
shoes.cpp:1:1: note: 'int64_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
  +++ |+#include <cstdint>
    1 | struct vec_queue