Submission #1087220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087220		peacebringer1667	Giraffes (JOI22_giraffes)	C++17	10 / 100	7075 ms	440 KiB

giraffes

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 8e3 + 5;

int a[maxn],pos[maxn];
namespace sub1{
	bool check(int n){
		return n <= 7;
	}
	
	bool good(const vector <int> &vec){
		int n = vec.size(),M = 0,m = n + 1;
		for (int l = 0 ; l < n - 2 ; l++){
		  M = 0;m = n + 1;
		  for (int r = l + 2 ; r < n ; r++){
		  	 M = max(M,vec[r - 1]);
		  	 m = min(m,vec[r - 1]);
		  	
		  	 if (M > max(vec[l],vec[r]) && m < min(vec[l],vec[r])) 
			     return 0;
		}
	 }
		return 1;
	}
	
	void solve(int n){
		vector <int> vec(n);
		for (int i = 0 ; i < n ; i++) vec[i] = i + 1;
		int res = n;
		
		do{
			int tmp = 0;
			if (good(vec)){
				
				for (int i = 1 ; i <= n ; i++)
				  tmp += (a[i] != vec[i - 1]);
			    res = min(res,tmp); 
			}
		} while (next_permutation(vec.begin(),vec.end()));
	    
	    cout << res;
	}
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int n;
	cin >> n;
	for (int i = 1 ; i <= n ; i++) cin >> a[i];
	
	
	sub1::solve(n);
    

	return 0;
}

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