Submission #936762

#	Time	Username	Problem	Language	Result	Execution time	Memory
936762		anton	Group Photo (JOI21_ho_t3)	C++17	44 / 100	5002 ms	708 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;
}

map<pii, int> store;
int dp(int val, int end){
    if(store.find({val, end})!= store.end()){
        return store[{val, end}];
    }
    else{
        int res = 0;
    
        if(val==0|| end == -1){
            res= 0;
        }
        else{
            res= 1e18;
            for(int i = 0; i<val; i++){   
                //cout<<"i is "<<i<<endl;   
                int c= 0;
                vector<int> begins;
                /*for(auto e: v){
                    cout<<e<<" ";
                }
                cout<<endl;*/
                for(int j = val-i; j<=val; j++){
                    begins.push_back(link[j]);
                    c+=move(j, end+val-i-j);
                }
                //cout<<val<<"cur c is "<<c<<endl;
                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();
                }
                /*for(auto e: v){
                    cout<<e<<" ";
                }
                cout<<endl;*/
            }
        }
        
        //cout<<val<<" "<<end<<" "<<res<<endl;
        store[{val, end}] = res;
        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 'int main()':
Main.cpp:84:9: warning: unused variable 'res' [-Wunused-variable]
   84 |     int res= 0;
      |         ^~~

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