Submission #527602

#	Time	Username	Problem	Language	Result	Execution time	Memory
527602		lcs147	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	518 ms	148848 KiB

shoes

#include"shoes.h"
#include<bits/stdc++.h>
// #define int long long
using namespace std;

struct fenwick {
    vector<int> fenw;
    fenwick(int n){
        fenw.assign(n, 0); // default value
    }
    int add(int a, int b) {
        return a+b;
    }
    void update(int x, int v) {
	    for(; x < fenw.size(); x |= (x + 1)) {
            fenw[x] = add(fenw[x], v);
        }
    }
    int query(int x) {  
        int sum = 0;
        for(; x >= 0; x = (x & (x + 1)) - 1) sum = add(sum, fenw[x]);
        return sum;
    }
};

long long count_swaps(vector<int>a) {

    map<int, deque<int>>id;
    for(int i=0; i<a.size(); i++) {
        id[a[i]].push_back(i);
    }

    fenwick bit(a.size());
    for(int i=0; i<a.size(); i++) {
        bit.update(i, +1);
    }

    vector<int>add(a.size());
    
    long long res = 0;
    for(int i=0; i<a.size(); i++) {
        if(i>0 && bit.query(i)-bit.query(i-1)==0) continue;

        int j = id[-a[i]].front();
    
        int swaps = bit.query(j) - bit.query(i);
        if(a[i]<0) swaps--;
        res += swaps;

        id[a[i]].pop_front();
        id[-a[i]].pop_front();
        bit.update(j, -1);
    }

    return res;
}

Compilation message (stderr)

shoes.cpp: In member function 'void fenwick::update(int, int)':
shoes.cpp:15:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |      for(; x < fenw.size(); x |= (x + 1)) {
      |            ~~^~~~~~~~~~~~~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0; i<a.size(); i++) {
      |                  ~^~~~~~~~~
shoes.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=0; i<a.size(); i++) {
      |                  ~^~~~~~~~~
shoes.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=0; i<a.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