oj.uz

Submission #331600

# Submission time Handle Problem Language Result Execution time Memory
331600 2020-11-29T05:20:56 Z limabeans Money (IZhO17_money) C++17
9 / 100
 1500 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;



bool test(int mask, vector<int> a) {
    int n = a.size();
    vector<int> w = {-1};
    for (int i=0; i<n-1; i++) {
	if (mask>>i&1) {
	    w.push_back(i);
	}
    }

    w.push_back(n-1);

    vector<vector<int>> v;
    for (int i=1; i<(int)w.size(); i++) {
	vector<int> tmp;
	for (int j=w[i-1]+1; j<=w[i]; j++) {
	    tmp.push_back(a[j]);
	}
	v.push_back(tmp);
    }


    // for (auto p: v) {
    // 	for (int x: p) cout<<x<<" ";
    // 	cout<<" | ";
    // }
    // cout<<endl;

    vector<int> res;

    for (auto p: v) {
	vector<int> nxt;

	bool done = false;
	for (int i=0; i<(int)res.size(); i++) {
	    if (done || res[i] <= p[0]) {
		nxt.push_back(res[i]);
	    } else {
		nxt.insert(nxt.end(), p.begin(), p.end());
		nxt.push_back(res[i]);
		done = true;
	    }
	}

	if (!done) {
	    nxt.insert(nxt.end(), p.begin(), p.end());
	}


	res = nxt;

	// watch(res.size());
	// for (int x: res) cout<<x<<" ";
	// cout<<endl;
	
    }


    // for (int x: res) cout<<x<<" ";
    // cout<<endl;

    assert((int)res.size() == n);

    bool ok = true;

    for (int i=1; i<n; i++) {
	ok &= (res[i]>=res[i-1]);
    }

    return ok;
}



int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    int n;
    cin>>n;
    vector<int> a(n);
    for (int i=0; i<n; i++) {
	cin>>a[i];
    }



    int ans = n;

    for (int mask=0; mask<(1<<(n-1)); mask++) {
	if (test(mask, a)) {
	    ans = min(ans, 1+__builtin_popcount(mask));
	}
    }


    cout<<ans<<endl;    
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 55 ms 364 KB Output is correct
18 Correct 24 ms 384 KB Output is correct
19 Correct 2 ms 364 KB Output is correct
20 Execution timed out 1595 ms 364 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 55 ms 364 KB Output is correct
18 Correct 24 ms 384 KB Output is correct
19 Correct 2 ms 364 KB Output is correct
20 Execution timed out 1595 ms 364 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 55 ms 364 KB Output is correct
18 Correct 24 ms 384 KB Output is correct
19 Correct 2 ms 364 KB Output is correct
20 Execution timed out 1595 ms 364 KB Time limit exceeded
21 Halted 0 ms 0 KB -