oj.uz

Submission #1056284

# Submission time Handle Problem Language Result Execution time Memory
1056284 2024-08-13T08:38:45 Z anton Giraffes (JOI22_giraffes) C++17
10 / 100
 7000 ms 436 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]);
            }
        }
    }
}

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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 428 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 428 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 8 ms 436 KB Output is correct
13 Correct 80 ms 412 KB Output is correct
14 Correct 800 ms 348 KB Output is correct
15 Execution timed out 7042 ms 348 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 428 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 8 ms 436 KB Output is correct
13 Correct 80 ms 412 KB Output is correct
14 Correct 800 ms 348 KB Output is correct
15 Execution timed out 7042 ms 348 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 428 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 8 ms 436 KB Output is correct
13 Correct 80 ms 412 KB Output is correct
14 Correct 800 ms 348 KB Output is correct
15 Execution timed out 7042 ms 348 KB Time limit exceeded
16 Halted 0 ms 0 KB -