Submission #540999

#	Time	Username	Problem	Language	Result	Execution time	Memory
540999		vinnipuh01	Money (IZhO17_money)	C++17	25 / 100	129 ms	308 KiB

money

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define int long long

using namespace std;

const long long oo = 1000000000000000000;

long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos;


/*
    ViHHiPuh

   (( `'-""``""-'` ))
     )-__-_.._-__-(
   / --- (o _ o) --- \
   \ .-* ( .0. ) *-. /
   _'-. ,_ '=' _, .-'_
  / `;#'#'# - #'#'#;` \
 \_)) -----'#'----- ((_/
      # --------- #
  '# ------- ------ #'
  /..-'# ------- #'-.\
  _\...-\'# -- #'/-.../_
  ((____)- '#' -(____))


    cout << fixed << setprecision(6) << x;

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    freopen ( "sum.in", "r", stdin )
*/

int n, a[ 1000001 ], mp[ 1000001 ];
vector <pair<int, int> > v;
set <int> vv;
int l, r;

main () {
	cin >> n;
	for ( int i = 0; i < n; i ++ )
		cin >> a[ i ];
	int bl;
	mn = oo;
	for ( int mask = 0; mask < ( 1 << n ); mask ++ ) {
		bl = ( mask & 1 );
		v.clear();
		vv.clear();
		ans = 0;
		l = 0;
		for ( int i = 0; i < n; i ++ ) {
			if ( (bool)( mask & ( 1 << i ) ) ^ (bool)bl ) {
				bl = mask & ( 1 << i );
				v.push_back( { l, i - 1 } );
				l = i;
			}
		}
		v.push_back( { l, n - 1 } );
		for ( auto i : v ) {
			for ( int j = i.first + 1; j <= i.second; j ++ ) {
				if ( a[ j ] < a[ j - 1 ] ) {
					ans = 1;
					break;
				}
			}
			if ( ans )
				break;
		}
		if ( ans )
			continue;
		for ( int j = v.front().first; j <= v.front().second; j ++ )
			vv.insert( a[ j ] );
		for ( int i = 1; i < v.size(); i ++ ) {
			auto it = vv.upper_bound( a[ v[ i ].first ] );
			if ( it != vv.end() && *it < a[ v[ i ].second ] ) {
				ans = 1;
				break;
			}
			for ( int j = v[ i ].first; j <= v[ i ].second; j ++ )
				vv.insert( a[ j ] );
		}
		if ( !ans ) {
			num = v.size();
			for ( auto i : v )
			mn = min( mn, num );
		}
	}
	cout << mn;
}

/*
6
3 6 4 5 1 2

*/

Compilation message (stderr)

money.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main () {
      | ^~~~
money.cpp: In function 'int main()':
money.cpp:85:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   for ( int i = 1; i < v.size(); i ++ ) {
      |                    ~~^~~~~~~~~~
money.cpp:96:15: warning: variable 'i' set but not used [-Wunused-but-set-variable]
   96 |    for ( auto i : v )
      |               ^

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