Submission #1289164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289164		eri16	Group Photo (JOI21_ho_t3)	C++20	12 / 100	529 ms	720 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);
        }
    } while (next_permutation(tm.begin(), tm.end()));
    return mn;
}

int solve_binary(vector <int> v){
    int n=v.size();
    int total=1<<(n); 

    vector <int> pos(n+1);
    
    for (int i=0; i<n; i++){pos[v[i]]=i;}

    int mn=INT_MAX;
    
    for (int mask=0; mask<total; mask++){
        vector<int> groups;
        for (int i=0; i<n; i++){
            if (mask&(1<<i)){
                groups.push_back(i+1);
            }
        }
        vector <pair<int,int>> tm;
        
        if (groups.size()!=0){
        int j=0;
        int lst=0;
        int lt=0;
        for (int i=0; i<n; i++){
            if (lst-1<i){
                if (j!=groups.size()){
                tm.push_back({groups[j],pos[groups[j]]});
                lst=groups[j];
                lt=lst;
                j++;}
                else{break;}
            }
            else{
                lt--;
                tm.push_back({lt,pos[lt]});
            }
        }
        vector<int> permutation;
        if (tm.size()==n){
        for (auto& p : tm){permutation.push_back(p.second);}
        int swaps=countInversions(permutation);
        mn=min(mn,swaps);}
            
        /*for (int i=0; i<tm.size(); i++){cout<<tm[i].first<<' ';}
        cout<<"\n";
        */
        groups.clear();
    }}
    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)<<"\n";
    cout<<solve_binary(v);
    
}

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