Submission #243893

#	Time	Username	Problem	Language	Result	Execution time	Memory
243893		AASG	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	254 ms	140324 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
int BIT[200010];int n;
 deque <int> de[100010];
 deque <int> iz[100010];
int V[200010];

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]--;
                update(p,-1);
                V[p1+1]++;
                update(p1+1,1);
                de[abs(s[i])].pop_front();
                iz[abs(s[i])].pop_front();
            }
        }else{
            int 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]--;
                update(p1,-1);
                V[p]++;
                update(p,1);
                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:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<s.size();i++){
                 ~^~~~~~~~~
shoes.cpp:32: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: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15