Submission #1102691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102691		toast12	Group Photo (JOI21_ho_t3)	C++14	12 / 100	405 ms	504 KiB

Main

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

const int INF = 1e9;

int n;
vector<int> idx;

int cost(vector<int> &p) {
    // check if the arrangement is valid
    for (int i = 0; i < n-1; i++) {
        if (p[i] >= p[i+1]+2) return INF;
    }
    int res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (idx[p[j]] < idx[p[i]]) res++;
        }
    }
    return res;
}

int main() {
    // n <= 20
    cin >> n;
    idx.resize(n+1);
    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
        idx[h[i]] = i;
    }
    int ans = INT_MAX;
    for (int mask = 0; mask < (1<<n); mask++) {
        vector<int> flip;
        for (int i = 0; i < n; i++) {
            if (mask & (1<<i)) flip.push_back(i);
        }
        if (flip.size() == 0 || (flip.size() > 1 && flip[0] == 0)) continue;
        vector<int> p(n);
        iota(p.begin(), p.end(), 1);
        int prev = 0;
        for (int i = 0; i < flip.size(); i++) {
            reverse(p.begin()+prev, p.begin()+flip[i]);
            prev = flip[i];
        }
        reverse(p.begin()+prev, p.end());
        ans = min(ans, cost(p));
        prev = 0;
        for (int i = 0; i < flip.size(); i++) {
            reverse(p.begin()+prev, p.begin()+flip[i]);
            prev = flip[i];
        }
        reverse(p.begin()+prev, p.end());
    }
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:42:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for (int i = 0; i < flip.size(); i++) {
      |                         ~~^~~~~~~~~~~~~
Main.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for (int i = 0; i < flip.size(); i++) {
      |                         ~~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 32
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36