제출 #1142942

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142942		Johan	Money (IZhO17_money)	C++20	25 / 100	232 ms	436 KiB

money

#include "bits/stdc++.h"
using namespace std;
#define int long long
# define ll long long

const int MAX = 262144 + 6;
const int LOG = 25;
const int inf = 1e18;
const int mod = 998244353;

bool sort(vector < int > &a){
  for(int i = 0; i < a.size() - 1; i++){
    if(a[i] > a[i + 1])
      return false;
  }
  return true;
}

void _(){
  int n, mn = inf;
  cin >> n;
  vector < int > a(n);
  for(int i = 0; i < n; i++)
    cin >> a[i];
  for(int i = 0; i < (1 << n); i++){
    int cnt = 1;
    vector < bool > vis(n, 0);
    for(int j = 0; j < n; j++){
      if(i & (1 << j)){
        vis[j] = 1;
        cnt++;  
      }
    }
    vis[n - 1] = 1;
    bool f = 1;
    vector < int > cur;
    for(int j = 0; j < n; j++){
      if(!vis[j]) cur.push_back(a[j]);
      else {
        cur.push_back(a[j]);
        if(!sort(cur)){f = 0;break;}
        cur.clear();  
      }
    }
    if(!f)  continue;
    bool ii = 1;
    vector < int > res;
    vector < int > ans;
    for(int fr = 0; fr < n; fr++){
      if(!vis[fr])  res.push_back(a[fr]);
      else {
        vector < int > all;
        res.push_back(a[fr]);
        if(!(int)ans.size()){
          for(auto ff : res)
            ans.push_back(ff);
          res.clear();
          continue;
        }
        int p1, p2;
        bool check = 0;
        if(res[res.size() - 1] <= ans[0]){
          for(auto ff : res)  all.push_back(ff);
          for(auto ff : ans)  all.push_back(ff);
          ans = all;
          res.clear();
          continue;
        }
        if(res[0] >= ans[ans.size() - 1]){
          for(auto ff : ans)  all.push_back(ff);
          for(auto ff : res)  all.push_back(ff);
          ans = all;
          res.clear();
          continue;
        }
        for(int ff = 0; ff < ans.size() - 1; ff++){
          if(ans[ff] <= res[0] && ans[ff + 1] >= res[res.size() - 1]){
            p1 = ff, p2 = ff + 1, check = 1;
            break; 
          }
        }
        if(!check){
          ii = 0;
          break;
        }
        else {
          for(int ff = 0; ff <= p1; ff++)  all.push_back(ans[ff]);
          for(auto ff : res)  all.push_back(ff);
          for(int ff = p2; ff < ans.size(); ff++)  all.push_back(ans[ff]);
          ans = all;
        }
        res.clear();
      }
    }
    if(ii)  mn = min(mn, cnt);
  }
  cout << mn << endl;
}

signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t = 1;
  // cin >> t;
  while(t--)  _();  
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 0 / 20
• Subtask 4: 0 / 55