Submission #581166

#	Time	Username	Problem	Language	Result	Execution time	Memory
581166		AngusWong	Group Photo (JOI21_ho_t3)	C++17	12 / 100	198 ms	304 KiB

Main

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

int n, a[5001], b[5001], l, mp[5001], ta[5001], t, ans=2e9;

int main() {
    cin >> n;
    for (int i=1; i<=n; i++) cin >> a[i];
    for (int mask=0; mask<(1<<n); mask++){
        if (__builtin_popcount(mask)%2) continue;
        for (int i=1; i<=n; i++) b[i]=i;
        l=-1;
        for (int i=0; i<n; i++){
            if (mask&(1<<i)){
                if (l==-1) l=i;
                else{
                    reverse(b+l+1, b+i+2);
                    l=-1;
                }
            }
        }
        for (int i=1; i<=n; i++) mp[b[i]]=i;
        for (int i=1; i<=n; i++) ta[i]=mp[a[i]];
        t=0;
        for (int i=1; i<=n; i++){
            for (int j=1; j<i; j++){
                if (ta[j]>ta[i]) t++;
            }
        }
        ans=min(ans, t);
    }
    cout << ans << "\n";
}

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