Submission #527300

#	Time	Username	Problem	Language	Result	Execution time	Memory
527300		Olympia	Arranging Shoes (IOI19_shoes)	C++17	45 / 100	972 ms	39072 KiB

shoes

#include <cmath>
#include <cassert>
#include <iostream>
#include <set>
#include <climits>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <type_traits>
#include <string>
#include <queue>
#include <map>
#include "shoes.h"

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
using namespace std;
struct segmentTree {
    vector<int64_t> v;
    vector<int64_t> val;

    int64_t ID = 0;

    int64_t op(int64_t a, int64_t b) {
        return a + b;
    }

    int64_t query(int dum, int tl, int tr, int& l, int& r) {
        if (tr < l || tl > r) {
            return ID;
        }
        if (tl >= l && tr <= r) {
            return val[dum];
        }
        int64_t mid = (tl + tr) >> 1;
        dum = dum << 1;
        return op(query(dum, tl, mid, l, r), query(dum + 1, mid + 1, tr, l, r));
    }

    int64_t query(int l, int r) {
        return query(1, 0, (int)v.size() - 1, l, r);
    }

    void update(int x, int64_t y) {
        int cur = (int) v.size() + x;
        int curX = x;
        int curY = x;
        while (true) {
            val[cur] = op(op(query(curX, x - 1), query(x + 1, curY)), y);
            if (cur == 0) {
                break;
            }
            if(cur % 2 == 0) {
                curY = 2 * curY - curX + 1;
            } else {
                curX = 2 * curX - curY - 1;
            }
            cur /= 2;
        }
    }

    void resz(int n) {
        v.resize((1 << (int) ceil(log2(n))));
        val.resize(v.size() * 2);
    }

};

int64_t get_inversions (vector<int> v) {
    segmentTree st;
    st.resz(v.size() + 3);
    int64_t ans = 0;
    for (int i = 0; i < v.size(); i++) {
        ans += st.query(v[i] + 1, v.size() + 2);
        st.update(v[i], st.query(v[i], v[i]) + 1);
    }
    return ans;
}

long long count_swaps (vector<int> v) {
    map<int,set<int>> myMap;
    for (int i = 0; i < v.size(); i++) {
        myMap[v[i]].insert(i);
    }
    vector<int> vec(v.size());
    int cntr = 0;
    for (int i = 0; i < v.size(); i++) {
        if (v[i] < 0) {
            int x = *myMap[-v[i]].begin();
            myMap[-v[i]].erase(x);
            vec[i] = cntr++;
            vec[x] = cntr++;
        }
    }
    return get_inversions(vec);
}

Compilation message (stderr)

shoes.cpp:16: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   16 | #pragma GCC optimization ("O3")
      | 
shoes.cpp:17: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   17 | #pragma GCC optimization ("Ofast")
      | 
shoes.cpp:18: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   18 | #pragma GCC optimization ("unroll-loops")
      | 
shoes.cpp: In function 'int64_t get_inversions(std::vector<int>)':
shoes.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:84:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
shoes.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~

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