oj.uz

Submission #1056280

# Submission time Handle Problem Language Result Execution time Memory
1056280 2024-08-13T08:37:21 Z anton Giraffes (JOI22_giraffes) C++17
0 / 100
 13 ms 1192 KB 
#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]);
            }
        }
    }
}

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;

    percalc_dist(a);
    while(ok){
        if(is_ok(cur_perm)){
            
            res = min(res, dist_begin[cur_perm]);
        }
        ok = next_permutation(cur_perm.begin(), cur_perm.end());
    }
    cout<<res*2<<endl;
}

Compilation message

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++){
      |                             ~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 440 KB Output is correct
8 Correct 12 ms 1192 KB Output is correct
9 Incorrect 13 ms 1116 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 440 KB Output is correct
8 Correct 12 ms 1192 KB Output is correct
9 Incorrect 13 ms 1116 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 440 KB Output is correct
8 Correct 12 ms 1192 KB Output is correct
9 Incorrect 13 ms 1116 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 440 KB Output is correct
8 Correct 12 ms 1192 KB Output is correct
9 Incorrect 13 ms 1116 KB Output isn't correct
10 Halted 0 ms 0 KB -