제출 #1289001

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289001		eri16	Group Photo (JOI21_ho_t3)	C++20	5 / 100	5092 ms	724 KiB

Main

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

int countInversions(vector<int>& arr) {
    int inv_count = 0;
    int n = arr.size();
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] > arr[j]) {
                inv_count++;
            }
        }
    }
    return inv_count;
}


int solve_perm(vector <int> v){
    
    vector <pair<int,int>> tm;
    
    for (int i=0; i<v.size(); i++){
        tm.push_back({v[i],i});
    }
    
    int mn=INT_MAX;
    
    sort(tm.begin(),tm.end());
    
    do {
        int ans=1;
        for (int i=1; i<tm.size(); i++){
            if (tm[i].first+2<=tm[i-1].first){
                ans=0;
            }
        }
        
        if (ans==1){
            
            vector<int> permutation;
            
            for (auto& p : tm) {
                permutation.push_back(p.second);
            }
            
            int swaps = countInversions(permutation);
            mn = min(mn, swaps);
            /*
            if (mn==swaps){
                for (int i=0; i<tm.size(); i++){
                    cout<<tm[i].first<<' ';
                }
                cout<<swaps<<"\n";
            }*/
            
        }
    } while (next_permutation(tm.begin(), tm.end()));
    
    return mn;
    
}

int main(){
    
    int n;
    
    cin>>n;
    
    vector <int> v(n);
    
    for (int i=0; i<n; i++){
        cin>>v[i];
    }
    
    cout<<solve_perm(v);
}

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