Submission #936753

#	Time	Username	Problem	Language	Result	Execution time	Memory
936753		anton	Group Photo (JOI21_ho_t3)	C++17	12 / 100	5045 ms	664 KiB

Main

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>
vector<int> v;
vector<int> link;

void swap_pos(int lh, int rh){
    int vlh = v[lh];
    int vrh = v[rh];
    link[vlh] = rh;
    link[vrh] = lh;
    swap(v[lh], v[rh]);
}

int move(int id, int pos){
    //cout<<"move "<<id<<" "<<pos<<endl;
    int cpos= link[id];
    int res = 0;
    if(cpos!=pos){
        for(; cpos<pos; cpos++){
            swap_pos(cpos,cpos+1);
            res++;
        }
        for(; pos<cpos; cpos--){
            swap_pos(cpos, cpos-1);
            res++;
        }
    }
    return res;
}


int dp(int val, int end){
    //cout<<val<<" "<<end<<endl;
    for(auto e: v){
        //cout<<e<<" ";
    }
    //cout<<endl;
    if(val==0|| end == -1){
        return 0;
    }
    int res= 1e18;
    for(int i = 0; i<val; i++){   
        //cout<<"i is "<<i<<endl;   
        int c= 0;
        vector<int> begins;
        for(int j = val-i; j<=val; j++){
            begins.push_back(link[j]);
            c+=move(j, end+val-i-j);
        }
        res=min(dp(val-i-1, end-i-1)+c, res);
        for(int j = val; j>=val-i; j--){
            move(j, begins.back());
            begins.pop_back();
        }

    }
    return res;
}

signed main(){
    int n;
    cin>>n;
    v.resize(n);
    link.resize(n+1);
    int res= 0;
    for(int i = 0; i<n; i++){
        cin>>v[i];
        link[v[i]] = i;
    }

    cout<<dp(n,n-1)<<endl;
    
}

Compilation message (stderr)

Main.cpp: In function 'long long int dp(long long int, long long int)':
Main.cpp:37:14: warning: unused variable 'e' [-Wunused-variable]
   37 |     for(auto e: v){
      |              ^
Main.cpp: In function 'int main()':
Main.cpp:68:9: warning: unused variable 'res' [-Wunused-variable]
   68 |     int res= 0;
      |         ^~~

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