| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 501833 | 2022-01-04T16:17:22 Z | Carmel_Ab1 | Money (IZhO17_money) | C++17 | 832 ms | 312 KB |
/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
*/
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>vi;
typedef vector<vector<int>>vvi;
typedef vector<ll>vl;
typedef vector<vl> vvl;
typedef pair<int,int>pi;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld,ld> pld;
typedef vector<pi> vpi;
//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T> ostream& operator<<(ostream& os, vector<T>& a){os<<"[";for(int i=0; i<ll(a.size()); i++){os << a[i] << ((i!=ll(a.size()-1)?" ":""));}os << "]\n"; return os;}
#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define outfl(x){cout << x << endl;return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map
template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p){is >> p.first >> p.second;return is;}
template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1, T2>& p){os <<"" << p.first << " " << p.second << ""; return os;}
void usaco(string taskname){
string fin = taskname + ".in";
string fout = taskname + ".out";
const char* FIN = fin.c_str();
const char* FOUT = fout.c_str();
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
}
template<typename T>
void read(vector<T>& v){
int n=v.size();
for(int i=0; i<n; i++)
cin >> v[i];
}
template<typename T>
vector<T>UNQ(vector<T>a){
vector<T>ans;
for(T t:a)
if(ans.empty() || t!=ans.back())
ans.push_back(t);
return ans;
}
void solve();
int main(){
GLHF;
int t=1;
//cin >> t;
while(t--)
solve();
}
bool ok(vi b,int l,int r){
for(int i=0; i+1<b.size(); i++)
if(b[i]<=l && r<=b[i+1])return 1;
return 0;
}
void solve() {
int n;
cin >> n;
vi a(n);
read(a);
if(is_sorted(all(a)))out(0)
int ans=1e9;
for(int i=1; i<(1<<(n)); i++){
vvi b={{}};
for(int j=0; j<n; j++){
if(i&(1<<j)){
b.back().pb(a[j]);
b.pb({});
}
else{
b.back().pb(a[j]);
}
}
if(!b.back().size())
b.pop_back();
bool okk=1;
for(int i=0; i<b.size(); i++)
okk&=(is_sorted(all(b[i])));
if(!okk)continue;
vi prv={int(-1e9),int(1e9)};
for(int x:b[0])
prv.pb(x);
sort(all(prv));
for(int i=1;okk && i<b.size(); i++){
int l=*min_element(all(b[i])),r=*max_element(all(b[i]));
bool has=0;
for(int j=0;!has && j+1<prv.size(); j++){
if((prv[j]<=l && r<=prv[j+1]))
has=1;
}
if(!has)
okk=0;
for(int x:b[i])
prv.pb(x);
sort(all(prv));
}
if(okk)
ans=min(ans,__builtin_popcount(i));
}
out(ans+1)
}
/*
6
3 6 4 5 1 2
*/
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 204 KB | Output is correct |
| 2 | Correct | 0 ms | 204 KB | Output is correct |
| 3 | Correct | 0 ms | 204 KB | Output is correct |
| 4 | Correct | 0 ms | 204 KB | Output is correct |
| 5 | Correct | 1 ms | 204 KB | Output is correct |
| 6 | Correct | 0 ms | 312 KB | Output is correct |
| 7 | Correct | 0 ms | 204 KB | Output is correct |
| 8 | Correct | 1 ms | 204 KB | Output is correct |
| 9 | Correct | 0 ms | 204 KB | Output is correct |
| 10 | Correct | 1 ms | 204 KB | Output is correct |
| 11 | Correct | 0 ms | 204 KB | Output is correct |
| 12 | Correct | 0 ms | 204 KB | Output is correct |
| 13 | Correct | 1 ms | 204 KB | Output is correct |
| 14 | Correct | 1 ms | 204 KB | Output is correct |
| 15 | Correct | 1 ms | 312 KB | Output is correct |
| 16 | Correct | 0 ms | 204 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 204 KB | Output is correct |
| 2 | Correct | 0 ms | 204 KB | Output is correct |
| 3 | Correct | 0 ms | 204 KB | Output is correct |
| 4 | Correct | 0 ms | 204 KB | Output is correct |
| 5 | Correct | 1 ms | 204 KB | Output is correct |
| 6 | Correct | 0 ms | 312 KB | Output is correct |
| 7 | Correct | 0 ms | 204 KB | Output is correct |
| 8 | Correct | 1 ms | 204 KB | Output is correct |
| 9 | Correct | 0 ms | 204 KB | Output is correct |
| 10 | Correct | 1 ms | 204 KB | Output is correct |
| 11 | Correct | 0 ms | 204 KB | Output is correct |
| 12 | Correct | 0 ms | 204 KB | Output is correct |
| 13 | Correct | 1 ms | 204 KB | Output is correct |
| 14 | Correct | 1 ms | 204 KB | Output is correct |
| 15 | Correct | 1 ms | 312 KB | Output is correct |
| 16 | Correct | 0 ms | 204 KB | Output is correct |
| 17 | Correct | 30 ms | 292 KB | Output is correct |
| 18 | Correct | 9 ms | 204 KB | Output is correct |
| 19 | Correct | 1 ms | 204 KB | Output is correct |
| 20 | Correct | 808 ms | 204 KB | Output is correct |
| 21 | Correct | 828 ms | 296 KB | Output is correct |
| 22 | Correct | 827 ms | 312 KB | Output is correct |
| 23 | Correct | 832 ms | 296 KB | Output is correct |
| 24 | Correct | 800 ms | 204 KB | Output is correct |
| 25 | Correct | 803 ms | 304 KB | Output is correct |
| 26 | Correct | 804 ms | 292 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 204 KB | Output is correct |
| 2 | Correct | 0 ms | 204 KB | Output is correct |
| 3 | Correct | 0 ms | 204 KB | Output is correct |
| 4 | Correct | 0 ms | 204 KB | Output is correct |
| 5 | Correct | 1 ms | 204 KB | Output is correct |
| 6 | Correct | 0 ms | 312 KB | Output is correct |
| 7 | Correct | 0 ms | 204 KB | Output is correct |
| 8 | Correct | 1 ms | 204 KB | Output is correct |
| 9 | Correct | 0 ms | 204 KB | Output is correct |
| 10 | Correct | 1 ms | 204 KB | Output is correct |
| 11 | Correct | 0 ms | 204 KB | Output is correct |
| 12 | Correct | 0 ms | 204 KB | Output is correct |
| 13 | Correct | 1 ms | 204 KB | Output is correct |
| 14 | Correct | 1 ms | 204 KB | Output is correct |
| 15 | Correct | 1 ms | 312 KB | Output is correct |
| 16 | Correct | 0 ms | 204 KB | Output is correct |
| 17 | Correct | 30 ms | 292 KB | Output is correct |
| 18 | Correct | 9 ms | 204 KB | Output is correct |
| 19 | Correct | 1 ms | 204 KB | Output is correct |
| 20 | Correct | 808 ms | 204 KB | Output is correct |
| 21 | Correct | 828 ms | 296 KB | Output is correct |
| 22 | Correct | 827 ms | 312 KB | Output is correct |
| 23 | Correct | 832 ms | 296 KB | Output is correct |
| 24 | Correct | 800 ms | 204 KB | Output is correct |
| 25 | Correct | 803 ms | 304 KB | Output is correct |
| 26 | Correct | 804 ms | 292 KB | Output is correct |
| 27 | Incorrect | 2 ms | 204 KB | Output isn't correct |
| 28 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 204 KB | Output is correct |
| 2 | Correct | 0 ms | 204 KB | Output is correct |
| 3 | Correct | 0 ms | 204 KB | Output is correct |
| 4 | Correct | 0 ms | 204 KB | Output is correct |
| 5 | Correct | 1 ms | 204 KB | Output is correct |
| 6 | Correct | 0 ms | 312 KB | Output is correct |
| 7 | Correct | 0 ms | 204 KB | Output is correct |
| 8 | Correct | 1 ms | 204 KB | Output is correct |
| 9 | Correct | 0 ms | 204 KB | Output is correct |
| 10 | Correct | 1 ms | 204 KB | Output is correct |
| 11 | Correct | 0 ms | 204 KB | Output is correct |
| 12 | Correct | 0 ms | 204 KB | Output is correct |
| 13 | Correct | 1 ms | 204 KB | Output is correct |
| 14 | Correct | 1 ms | 204 KB | Output is correct |
| 15 | Correct | 1 ms | 312 KB | Output is correct |
| 16 | Correct | 0 ms | 204 KB | Output is correct |
| 17 | Correct | 30 ms | 292 KB | Output is correct |
| 18 | Correct | 9 ms | 204 KB | Output is correct |
| 19 | Correct | 1 ms | 204 KB | Output is correct |
| 20 | Correct | 808 ms | 204 KB | Output is correct |
| 21 | Correct | 828 ms | 296 KB | Output is correct |
| 22 | Correct | 827 ms | 312 KB | Output is correct |
| 23 | Correct | 832 ms | 296 KB | Output is correct |
| 24 | Correct | 800 ms | 204 KB | Output is correct |
| 25 | Correct | 803 ms | 304 KB | Output is correct |
| 26 | Correct | 804 ms | 292 KB | Output is correct |
| 27 | Incorrect | 2 ms | 204 KB | Output isn't correct |
| 28 | Halted | 0 ms | 0 KB | - |