Submission #380813

#	Time	Username	Problem	Language	Result	Execution time	Memory
380813		Karliver	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1093 ms	3200 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#include <fstream>
#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;
typedef complex<ll> G;
const int INF = 1e9 + 1;
const int N = 1e6;
const double eps = 1e-3;

using namespace std;
long long count_swaps(std::vector<int> a) {
    int n = a.size();
    int ans = 0;
    vector<bool> vis(n, false);
    for(int i =0;i < n;i += 2) {
        assert(i + 1 < n);
        if(a[i] < 0 && a[i + 1] == a[i] * -1) {
            vis[i] = 1;
            vis[i + 1] = 1;
            continue;
        }
        int f = a[i] * -1;
        int id = -1;
        for(int j = i + 1;j < n;++j) {
            if(!vis[j] && a[j] == f) {
                id = j;
                break;
            }

        }
        int from = i;
        assert(id != -1);
        if(a[i] < 0) {
            if(id > from)from++;
        }
        if(a[i] > 0) {
            if(id < from)from--;
        }
        if(from > id)swap(id, from);
        //cout << from << ' ' << id << '\n';
        while(id > from) {
            swap(a[id], a[id - 1]);
            --id;
            ++ans;
        }
        vis[i] = 1;
        vis[i + 1] = 1;
    }
    return ans;
}

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