Submission #735309

#	Time	Username	Problem	Language	Result	Execution time	Memory
735309		That_Salamander	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	413 ms	153952 KiB

shoes

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <cstring>
#include <queue>
#include <unordered_set>
#include <unordered_map>

#define FOR(var,bound) for(int var = 0; var < bound; var++)
#define FORB(var,lb,ub) for (int var = lb; var < ub; var++)
#define FORR(var,bound) for(int var = bound-1; var >= 0; var--)

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

ll countSwapsAndSort(vector<int>& s) {
    if (s.size() == 1) return 0;
    if (s.size() == 2) {
        if (s[0] > s[1]) {
            swap(s[0], s[1]);
            return 1;
        }

        return 0;
    }

    vector<int> left, right;
    int m = s.size() / 2;

    FOR(i, m) {
        left.push_back(s[i]);
    }

    FORB(i, m, s.size()) {
        right.push_back(s[i]);
    }

    ll res = 0;
    res += countSwapsAndSort(left);
    res += countSwapsAndSort(right);

    s.clear();

    int iLeft = 0;
    int iRight = 0;

    while (iLeft < left.size() && iRight < right.size()) {
        if (left[iLeft] < right[iRight]) {
            s.push_back(left[iLeft++]);
        } else {
            res += (left.size() - iLeft);
            s.push_back(right[iRight++]);
        }
    }

    FORB(i, iLeft, left.size()) s.push_back(left[i]);
    FORB(i, iRight, right.size()) s.push_back(right[i]);

    return res;
}

/*ll count_swaps(vector<int> s) {
    vector<int> perm(s.size());
    FOR(i, s.size()) perm[i] = i;
    ll res = 1000000000000000000ll;

    do {
        bool valid = true;
        for (int i = 0; i < s.size(); i += 2) {
            if (s[perm[i]] > 0 || s[perm[i + 1]] < 0) {
                valid = false;
                break;
            }

            if (s[perm[i]] != -s[perm[i + 1]]) {
                valid = false;
                break;
            }
        }

        if (!valid) continue;

        vector<int> inv(s.size());
        FOR(i, s.size()) {
            inv[perm[i]] = i;
        }

        res = min(res, countSwapsAndSort(inv));
    } while(next_permutation(perm.begin(), perm.end()));

    return res;
}*/

ll count_swaps(vector<int> s) {
    unordered_map<int, queue<int>> last;
    set<pair<int, int>> pairs;

    FOR(i, s.size()) {
        int x = s[i];
        if (last[-x].size()) {
            pairs.insert({last[-x].front(), i});
            last[-x].pop();
        } else {
            last[x].push(i);
        }
    }

    vector<int> inv(s.size());
    int i = 0;

    for (auto p: pairs) {
        if (s[p.first] > 0) swap(p.first, p.second);
        inv[p.first] = i++;
        inv[p.second] = i++;
    }

    return countSwapsAndSort(inv);
}

#ifdef LOCAL_TEST
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> s(n * 2);

    for (int& i: s) cin >> i;

    cout << "Result: " << count_swaps(s) << endl;
}
#endif

Compilation message (stderr)

shoes.cpp: In function 'll countSwapsAndSort(std::vector<int>&)':
shoes.cpp:14:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define FORB(var,lb,ub) for (int var = lb; var < ub; var++)
......
   42 |     FORB(i, m, s.size()) {
      |          ~~~~~~~~~~~~~~                         
shoes.cpp:42:5: note: in expansion of macro 'FORB'
   42 |     FORB(i, m, s.size()) {
      |     ^~~~
shoes.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     while (iLeft < left.size() && iRight < right.size()) {
      |            ~~~~~~^~~~~~~~~~~~~
shoes.cpp:55:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     while (iLeft < left.size() && iRight < right.size()) {
      |                                   ~~~~~~~^~~~~~~~~~~~~~
shoes.cpp:14:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define FORB(var,lb,ub) for (int var = lb; var < ub; var++)
......
   64 |     FORB(i, iLeft, left.size()) s.push_back(left[i]);
      |          ~~~~~~~~~~~~~~~~~~~~~                  
shoes.cpp:64:5: note: in expansion of macro 'FORB'
   64 |     FORB(i, iLeft, left.size()) s.push_back(left[i]);
      |     ^~~~
shoes.cpp:14:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define FORB(var,lb,ub) for (int var = lb; var < ub; var++)
......
   65 |     FORB(i, iRight, right.size()) s.push_back(right[i]);
      |          ~~~~~~~~~~~~~~~~~~~~~~~                
shoes.cpp:65:5: note: in expansion of macro 'FORB'
   65 |     FORB(i, iRight, right.size()) s.push_back(right[i]);
      |     ^~~~
shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:13:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define FOR(var,bound) for(int var = 0; var < bound; var++)
......
  106 |     FOR(i, s.size()) {
      |         ~~~~~~~~~~~                          
shoes.cpp:106:5: note: in expansion of macro 'FOR'
  106 |     FOR(i, s.size()) {
      |     ^~~

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