Submission #513785

#	Time	Username	Problem	Language	Result	Execution time	Memory
513785		Mazaalai	Money (IZhO17_money)	C++17	100 / 100	211 ms	19864 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

money

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast, unroll-loops")
#pragma GCC target("avx,avx2,fma")
#define pb push_back
#define LINE "-----------------\n"
#define ALL(x) x.begin(),x.end()
using namespace std;
int n, m;
const int N = 1e6 + 5;
const int M = 1e6 + 1;
int cnt[N], nx[N], pv[N], nums[N], sorted[N];
int nn, mm, x, i, ans, j, curCnt, a, b;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> x;
		cnt[x]++;
		nums[nn++] = x;
	}
	for (i = 1; i < M; i++) {
		if (cnt[i] > 0) {
			sorted[mm++] = i;
			// sorted.pb(i);
		}
	}
	nx[0] = sorted[0];
	pv[sorted[0]] = 0;
	nx[sorted[mm-1]] = M;
	pv[M] = sorted[mm-1];
	for (i = 0; i < mm-1; i++) {
		nx[sorted[i]] = sorted[i+1];
		pv[sorted[i+1]] = sorted[i];
	}
	for (i = n - 1; i >= 0; i--) {
		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) {
					a = pv[nums[j+1]], b = nx[nums[j+1]];
					nx[a] = b;
					pv[b] = a;
				}
				border = 0;
				curCnt = 1;
			}
		}
		cnt[nums[j+1]] -= curCnt;
		if (cnt[nums[j+1]] == 0) {
			a = pv[nums[j+1]], b = nx[nums[j+1]];
			nx[a] = b;
			pv[b] = a;
		}
		ans++;
		i = j+1;
	}
	cout << ans << '\n';
}

Compilation message (stderr)

money.cpp:3:43: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    3 | #pragma GCC optimize("Ofast, unroll-loops")
      |                                           ^
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
    4 | #pragma GCC target("avx,avx2,fma")
      |                                  ^
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
money.cpp:4:34: warning: bad option '-f unroll-loops' to attribute 'o

Subtask 19 / 9

#	Verdict	Execution time	Memory	Grader output
Fetching results...

Subtask 216 / 16

#	Verdict	Execution time	Memory	Grader output
Fetching results...

Subtask 320 / 20

#	Verdict	Execution time	Memory	Grader output
Fetching results...

Subtask 455 / 55

#	Verdict	Execution time	Memory	Grader output
Fetching results...