Submission #1040061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040061		LaMatematica14	Arranging Shoes (IOI19_shoes)	C++17	30 / 100	37 ms	7224 KiB

shoes

#include <bits/stdc++.h>
using namespace std;

long long count_swaps(vector<int> S) {
    vector<int> fat(10, 1);
    for (int i = 1; i < 10; i++) fat[i] = fat[i-1]*i;
    int n = S.size();
    vector<int> c = S;
    sort(c.rbegin(), c.rend());
    vector<int> sz(n/2);
    for (int i = 0; i < n/2; i++) sz[i] = c[i];
    long long best = 1e9;
    for (int j = 0; j < fat[n/2]; j++) {
        long long tot = 0;
        next_permutation(sz.begin(), sz.end());
        vector<queue<int>> a(n);
        for (int i = 0; i < n/2; i++) {
            a[sz[i]].push(2*i);
        }
        vector<int> pa(n);
        int att = 0;
        for (long long i = 0; i < n; i++) {
            if (S[i] < 0) {
                pa[i] = a[-S[i]].front();
                a[-S[i]].pop();
                a[-S[i]].push(pa[i]);
            }
        }
        for (long long i = 0; i < n; i++) {
            if (S[i] > 0) {
                pa[i] = a[S[i]].front()+1;
                a[S[i]].pop();
            }
        }
        for (long long i = 0; i < n; i++) {
            for (long long j = i+1; j < n; j++) {
                if (pa[i] > pa[j]) tot++;
            }
        }
        best = min(best, tot);
    }
    return best;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:21:13: warning: unused variable 'att' [-Wunused-variable]
   21 |         int att = 0;
      |             ^~~

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