oj.uz

Submission #1056376

# Submission time Handle Problem Language Result Execution time Memory
1056376 2024-08-13T09:04:34 Z anton Giraffes (JOI22_giraffes) C++17
32 / 100
 7000 ms 2072 KB 
#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

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.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 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
22.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 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 64 ms 348 KB Output is correct
18 Correct 64 ms 348 KB Output is correct
19 Correct 5 ms 348 KB Output is correct
20 Correct 11 ms 540 KB Output is correct

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 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 64 ms 348 KB Output is correct
18 Correct 64 ms 348 KB Output is correct
19 Correct 5 ms 348 KB Output is correct
20 Correct 11 ms 540 KB Output is correct
21 Execution timed out 7075 ms 2072 KB Time limit exceeded
22 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 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 64 ms 348 KB Output is correct
18 Correct 64 ms 348 KB Output is correct
19 Correct 5 ms 348 KB Output is correct
20 Correct 11 ms 540 KB Output is correct
21 Execution timed out 7075 ms 2072 KB Time limit exceeded
22 Halted 0 ms 0 KB -