Submission #513643

#TimeUsernameProblemLanguageResultExecution timeMemory
513643MazaalaiMoney (IZhO17_money)C++17
0 / 100
0 ms332 KiB
#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';
      |                                       ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...