Submission #266615

#	Time	Username	Problem	Language	Result	Execution time	Memory
266615		doowey	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	349 ms	275320 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = (int)2e5 + 10;
queue<int> pos[2][N];
bool active[N];

int lim;
int tree[N * 2];

void upd(int x, int v){
    x += lim;
    tree[x]=v;
    x /= 2;
    while(x > 0){
        tree[x]=tree[x*2]+tree[x*2+1];
        x /= 2;
    }
}

int get(int l, int r){
    l += lim;
    r += lim;
    int res = 0;
    while(l <= r){
        if(l % 2 == 1) res += tree[l++];
        if(r % 2 == 0) res += tree[r--];
        l /= 2;
        r /= 2;
    }
    return res;
}

ll count_swaps(vector<int> s) {
    lim = (int)s.size();

    int n = (int)s.size() / 2;
    for(int i = 0 ; i < s.size(); i ++ ){
        if(s[i] < 0){
            pos[0][-s[i]].push(i);
        }
        else{
            pos[1][s[i]].push(i);
        }
        active[i]=true;
        upd(i, 1);
    }

    ll res = 0;
    int d, x;
    int nx;
    for(int i = 0 ; i < s.size(); i ++ ){
        if(!active[i]) continue;
        x = s[i];
        d = 1;
        if(x < 0){
            x = -x;
            d = 0;
        }
        nx = pos[(d ^ 1)][x].front();
        pos[(d ^ 1)][x].pop();
        pos[d][x].pop();
        res += get(i + 1, nx - 1) + d;
        active[i]=false;
        active[nx]=false;
        upd(i,0);
        upd(nx,0);
    }
    return res;
}

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i = 0 ; i < s.size(); i ++ ){
      |                     ~~^~~~~~~~~~
shoes.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i = 0 ; i < s.size(); i ++ ){
      |                     ~~^~~~~~~~~~
shoes.cpp:46:9: warning: unused variable 'n' [-Wunused-variable]
   46 |     int n = (int)s.size() / 2;
      |         ^

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