Submission #243886

#	Time	Username	Problem	Language	Result	Execution time	Memory
243886		AASG	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	53 ms	67708 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
int BIT[100010];int n;
 deque <int> de[50000];
 deque <int> iz[50000];
int V[100010];
void update(int x, int val)
{
      for(; x <= n; x += x&-x)
        BIT[x] += val;
}
int query(int x)
{
     int sum = 0;
     for(; x > 0; x -= x&-x)
        sum += BIT[x];
     return sum;
}

long long count_swaps(vector<int> s) {
    n=s.size()+1;
    long long r=0;
    for(int i=0;i<s.size();i++){
        if(s[i]<0){
            iz[abs(s[i])].push_back(i+1);
        }else{
        de[s[i]].push_back(i+1);
        }
        V[i+1]=1;
        update(i+1,V[i+1]);
    }

    for(int i=0;i<s.size();i++){
        if(s[i]<0){
            int p1;
            p1=iz[abs(s[i])].front();
            if(iz[abs(s[i])].size()>0 && p1==i+1){
                int p=de[abs(s[i])].front();
                r=r+abs(query(p)-query(p1)-1);
                V[p]=0;
                update(p,V[p]);
                V[p1+1]++;
                update(p1,V[p1]);
                de[abs(s[i])].pop_front();
                iz[abs(s[i])].pop_front();
            }
        }else{
            long p=de[abs(s[i])].front();
            if(de[abs(s[i])].size()>0 && p==i+1){
                int p1=iz[abs(s[i])].front();
                r=r+abs(query(p)-query(p1));
                V[p1]=0;
                update(p1,V[p1]);
                V[p]++;
                update(p,V[p]);
                de[abs(s[i])].pop_front();
                iz[abs(s[i])].pop_front();
            }
        }
    }
	return r;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<s.size();i++){
                 ~^~~~~~~~~
shoes.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<s.size();i++){
                 ~^~~~~~~~~

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