Submission #1056376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056376		anton	Giraffes (JOI22_giraffes)	C++17	32 / 100	7075 ms	2072 KiB

giraffes

#include<bits/stdc++.h>

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

const int MAX_N=  7;
int N;
vector<int> a;

bool is_ok(vector<int>&v){
    for(int r = 0; r<v.size(); r++){
        int min_inter = v[r];
        int max_inter = v[r];
        for(int l = r-1; l>=0; l--){
            min_inter = min(min_inter, v[l]);
            max_inter = max(max_inter, v[l]);
            if(min_inter< v[l] && min_inter < v[r]){
                if(max_inter> v[r] && max_inter> v[l]){
                    return false;
                }
            }
        }
    }
    return true;
}

int iter_valid_perm(vector<int>& cur_pref, vector<bool>& used, int cur_cost){
    
    if(cur_pref.size() == N){
        return 0;
    }
    else{
        int res= 1e18;
        for(int j = a[cur_pref.size()]; j!=a[cur_pref.size()]+N; j=j+1 ){
            int i = j%N;
            if(!used[i]){
                used[i] = true;
                cur_pref.push_back(i);
                if(is_ok(cur_pref)){
                    if(i == a[cur_pref.size()-1]){
                        res = min(res, iter_valid_perm(cur_pref, used, cur_cost));
                    }
                    else{
                        res = min(res, iter_valid_perm(cur_pref, used, cur_cost+1)+1);
                    }
                }
                cur_pref.pop_back();
                used[i] = false;
            }
        }
        return res;

    }
}


void recur_subset(vector<vector<int>>& res, vector<int>& cur, int target_len){
    if(cur.size() == target_len){
        res.push_back(cur);
    }
    int prev= -1;
    if(cur.size()>0){
        prev = cur.back();
    }
    for(int i = prev+1; i<N; i++){
        cur.push_back(i);
        recur_subset(res, cur, target_len);
        cur.pop_back();
    }
}
vector<vector<int>> subsets(int len){
    vector<vector<int>> res;
    vector<int> cur;
    recur_subset(res, cur, len);
    return res;
} 
int get_dist(vector<int> begin){
    
    if(is_ok(begin)){
        return 0;
    }
    vector<int> cur;
    for(int target_count = 2; target_count<=N; target_count++){
        for(auto subset: subsets(target_count)){
            vector<int> initial_subset = subset;
            bool ok = true;

            while(ok){
                cur = begin;
                for(int i = 0; i<initial_subset.size(); i++){
                    cur[initial_subset[i]] = begin[subset[i]]; 
                }
                if(is_ok(cur)){
                    return target_count;
                }
                ok = next_permutation(subset.begin(), subset.end());
            }
        }
    }
}

signed main(){
    cin>>N;
    a.resize(N);
    for(int i = 0; i<N; i++){
        cin>>a[i];
        a[i]--;
    }

    cout<<get_dist(a)<<endl;
}

Compilation message (stderr)

giraffes.cpp: In function 'bool is_ok(std::vector<long long int>&)':
giraffes.cpp:12:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int r = 0; r<v.size(); r++){
      |                    ~^~~~~~~~~
giraffes.cpp: In function 'long long int iter_valid_perm(std::vector<long long int>&, std::vector<bool>&, long long int)':
giraffes.cpp:30:24: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   30 |     if(cur_pref.size() == N){
      |        ~~~~~~~~~~~~~~~~^~~~
giraffes.cpp: In function 'void recur_subset(std::vector<std::vector<long long int> >&, std::vector<long long int>&, long long int)':
giraffes.cpp:59:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   59 |     if(cur.size() == target_len){
      |        ~~~~~~~~~~~^~~~~~~~~~~~~
giraffes.cpp: In function 'long long int get_dist(std::vector<long long int>)':
giraffes.cpp:91:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |                 for(int i = 0; i<initial_subset.size(); i++){
      |                                ~^~~~~~~~~~~~~~~~~~~~~~
giraffes.cpp:83:17: warning: control reaches end of non-void function [-Wreturn-type]
   83 |     vector<int> cur;
      |                 ^~~

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 41