oj.uz

Submission #173041

# Submission time Handle Problem Language Result Execution time Memory
173041 2020-01-03T08:05:43 Z tourist Money (IZhO17_money) C++14
9 / 100
 3 ms 380 KB 
#include <iostream>
#include <vector>

using namespace std;

#define ll long long
#define sz(x) (int)x.size()
#define pii pair < int, int >
#define endl "\n"
#define METH ios::sync_with_stdio(0); cin.tie(0);
#define BEGIN cout << "BEGIN" << endl;
#define END cout << "END" << endl;

const int mod = 1e9 + 7;															/// ANOTHER HASH MOD: 228228227
const int prime = 29;																	/// ANOTHER HASH PRIME: 997
const int INF = ((long long) 0xCAFEBABE - 1e9 - 4e8);

int n;
vector < int > v, nw;

inline void purify() {
}

inline void precalc() {
}

inline void read() {
	v.push_back(0);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int a; scanf("%d", &a);
		v.push_back(a);
	}
}

bool sorted(int l, int r) {
	for (int i = l; i < r; i++) {
		if (v[i] > v[i + 1]) {
			return false;
		}
	}

	return true;
}

int check(int l, int r) {
	if (sorted(l, r)) {
		if (nw.size() == 0) {
			return 0;
		}

		if (nw.size() == 1) {
			if (v[l] >= nw[0]) {
				return 0;
			} else {
				return -1;
			}
		}

		for (int i = 1; i < nw.size(); i++) {
			if (nw[i - 1] <= v[l] && v[r] <= nw[i]) {
				return (i - 1);
			}
		}

		if (v[r] <= nw[0]) {
			return -1;
		}

		if (nw.back() <= v[l]) {
			return nw.size();
		}
	}

	return -2;
}

void put(int l, int r, int place) {
	vector < int > temp;
	for (int i = 0; i <= place && i < nw.size(); i++) {
		temp.push_back(nw[i]);
	}

	for (int i = l; i <= r; i++) {
		temp.push_back(v[i]);
	}

	for (int i = place + 1; i < nw.size(); i++) {
		temp.push_back(nw[i]);
	}

	nw = temp;
}

inline void solve() {
	int l = 1, ans = 0;
	for (int r = 1; r <= n; r++) {
		if (check(l, r) == -2) {
			put(l, r - 1, check(l, r - 1));
			ans++;
			l = r;
			r--;
		} else if (r == n) {
			put(l, r, check(l, r));
			ans++;
			break;
		}
	}

	cout << ans << endl;
}

int main() {
	int t = 1;
	//scanf("%d", &t);

	//precalc();
	while (t--) {
		//purify();
		read();
		solve();
	}
}

Compilation message

money.cpp: In function 'int check(int, int)':
money.cpp:60:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < nw.size(); i++) {
                   ~~^~~~~~~~~~~
money.cpp: In function 'void put(int, int, int)':
money.cpp:80:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i <= place && i < nw.size(); i++) {
                                ~~^~~~~~~~~~~
money.cpp:88:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = place + 1; i < nw.size(); i++) {
                          ~~^~~~~~~~~~~
money.cpp: In function 'void read()':
money.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
money.cpp:31:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a; scanf("%d", &a);
          ~~~~~^~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 360 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 252 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Incorrect 3 ms 256 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 360 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 252 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Incorrect 3 ms 256 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 360 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 252 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Incorrect 3 ms 256 KB Output isn't correct
21 Halted 0 ms 0 KB -