Submission #513643

#	Time	Username	Problem	Language	Result	Execution time	Memory
513643		Mazaalai	Money (IZhO17_money)	C++17	0 / 100	0 ms	332 KiB

money

#include <bits/stdc++.h>
#define pb push_back
#define LINE "-----------------\n"
#define ALL(x) x.begin(),x.end()
using namespace std;
int n, m;
vector <int> nums, sorted;
const int N = 1e6 + 5;
const int M = 1e6 + 1;
int cnt[N], nx[N], pv[N];
void print(vector<int>x) {
	for (auto el : x) cout << el << " "; cout << '\n';
}
void showList() {
	cout << "LIST: ";
	int x = nx[0];
	while(x != M) {
		cout << x << ' ';
		x = nx[x];
	}
	cout << '\n';
	cout << "TSIL: ";
	x = pv[M];
	while(x != 0) {
		cout << x << ' ';
		x = pv[x];
	}
	cout << '\n';
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x; cin >> x;
		cnt[x]++;
		nums.pb(x);
		sorted.pb(x);
	}
	sort(ALL(sorted));
	nx[0] = sorted[0];
	pv[sorted[0]] = 0;
	for (int i = 0; i < n - 1; i++) {
		if (sorted[i] != sorted[i+1]) {
			nx[sorted[i]] = sorted[i+1];
			pv[sorted[i+1]] = sorted[i];
		}
	}
	nx[sorted.back()] = M;
	pv[M] = sorted.back();
	int ans = 0;
	for (int i = n - 1; i >= 0; i--) {
		int j, curCnt = 1;
		bool border = 1;
		for (j = i-1; j >= 0; j--) {
			if (nums[j] == nums[j+1]) {
				curCnt++;
				continue;
			} else {
				if (nx[nums[j]] != nums[j+1]) break;
				if (!border || curCnt != cnt[nums[j+1]]) break;
				cnt[nums[j+1]] -= curCnt;
				if (cnt[nums[j+1]] == 0) {
					int a = pv[nums[j+1]], b = nx[nums[j+1]];
					// cout << "REMOVE: " << nums[j+1] << " " << a << ',' << b << '\n';
					nx[a] = b;
					pv[b] = a;
				}
				border = 0;
				curCnt = 1;
			}
			// showList();
		}
		// cout << LINE;
		// for (int k = j+1; k <= i; k++) cout << nums[k] << " \n"[k==i];
		cnt[nums[j+1]] -= curCnt;
		if (cnt[nums[j+1]] == 0) {
			int a = pv[nums[j+1]], b = nx[nums[j+1]];
			// cout << "REMOVE: " << nums[j+1] << " " << a << ',' << b << '\n';
			nx[a] = b;
			pv[b] = a;
		}
		// showList();
		ans++;
		i = j+1;
	}
	cout << ans << '\n';
}

Compilation message (stderr)

money.cpp: In function 'void print(std::vector<int>)':
money.cpp:12:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   12 |  for (auto el : x) cout << el << " "; cout << '\n';
      |  ^~~
money.cpp:12:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   12 |  for (auto el : x) cout << el << " "; cout << '\n';
      |                                       ^~~~

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