제출 #513775

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
513775		Mazaalai	Money (IZhO17_money)	C++17	100 / 100	175 ms	20140 KiB

money

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#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];

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));
	for (int i = 1; i < M; i++) {
		if (cnt[i] > 0) sorted.pb(i);
	}
	nx[0] = sorted[0];
	pv[sorted[0]] = 0;
	for (int i = 0; i < sorted.size()-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, j, curCnt, a, b; 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';
}

컴파일 시 표준 에러 (stderr) 메시지

money.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      | 
money.cpp: In function 'int main()':
money.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for (int i = 0; i < sorted.size()-1; i++) {
      |                  ~~^~~~~~~~~~~~~~~~~

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