Submission #1056284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056284		anton	Giraffes (JOI22_giraffes)	C++17	10 / 100	7042 ms	436 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;

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;
}
map<vector<int>, int> dist_begin;

void percalc_dist(vector<int> begin){
    dist_begin[begin]= 0;
    deque<vector<int>> dq;

    dq.push_back(begin);

    while(dq.size()>0){
        auto e = dq.front();
        dq.pop_front();
        int dist = dist_begin[e];
        for(int l = 0; l<begin.size(); l++){
            for(int r= l+1; r<begin.size(); r++){
                swap(e[l], e[r]);
                if(dist_begin.find(e)== dist_begin.end()){
                    dist_begin[e] = dist+1;
                    dq.push_back(e);
                }
                swap(e[l], e[r]);
            }
        }
    }
}

int get_dist(vector<int>&a, vector<int>& b){
    int res= 0;
    for(int i = 0; i<a.size(); i++){
        if(a[i]!=b[i]){
            res++;
        }
    }
    return res;
}

signed main(){
    cin>>N;

    vector<int> a(N);
    for(int i = 0; i<N; i++){
        cin>>a[i];
        a[i]--;
    }

    int res= 1e18;
    vector<int> cur_perm;
    for(int i = 0; i<N; i++){
        cur_perm.push_back(i);
    }
    bool ok = true;

    while(ok){
        if(is_ok(cur_perm)){
            
            res = min(res, get_dist(cur_perm, a));
        }
        ok = next_permutation(cur_perm.begin(), cur_perm.end());
    }
    cout<<res<<endl;
}

Compilation message (stderr)

giraffes.cpp: In function 'bool is_ok(std::vector<long long int>&)':
giraffes.cpp:11: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]
   11 |     for(int r = 0; r<v.size(); r++){
      |                    ~^~~~~~~~~
giraffes.cpp: In function 'void percalc_dist(std::vector<long long int>)':
giraffes.cpp:38:25: 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]
   38 |         for(int l = 0; l<begin.size(); l++){
      |                        ~^~~~~~~~~~~~~
giraffes.cpp:39:30: 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]
   39 |             for(int r= l+1; r<begin.size(); r++){
      |                             ~^~~~~~~~~~~~~
giraffes.cpp: In function 'long long int get_dist(std::vector<long long int>&, std::vector<long long int>&)':
giraffes.cpp:53: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]
   53 |     for(int i = 0; i<a.size(); i++){
      |                    ~^~~~~~~~~

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