Submission #1196182

#TimeUsernameProblemLanguageResultExecution timeMemory
1196182Mousa_Aboubaker서열 (APIO23_sequence)C++20
0 / 100
149 ms33608 KiB
#include "sequence.h" #include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <typename T> using o_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; int sequence(int N, vector<int> A) { // subtask 4 // binary search for the answer for the case of 1 and 3 // the case of 2, sort all the array, and remove elements greedily until you get 2 as the median // this is if there was 3 distinct numbers // in case of only 2 distinct, return the maximum of them // in case of only 1 distinct number, return N map<int, int> mp; for(int i = 0; i < N; i++) mp[A[i]]++; if(mp.size() == 1) { return mp.begin()->second; } if(mp.size() == 2) { return max(mp.begin()->second, mp.rbegin()->second); } // we got 1, 2, 3 in our sequence vector idx(4, deque<int>()); for(int i = 0; i < N; i++) idx[A[i]].push_back(i); vector pref(N + 1, vector<int>(4)); for(int i = 0; i < N; i++) { if(i) pref[i] = pref[i - 1]; pref[i][A[i]]++; } int mx = 1; int l = 1, r = mp[1], ans = 1; while(l <= r) { int md = (l + r) / 2; bool can = false; for(int i = md - 1; i < idx[1].size(); i++) { int j = idx[1][i]; int k = idx[1][i - md + 1]; int p = pref[j][1] - (k ? pref[k - 1][1] : 0); int others = j - k + 1 - p; int all = p + others; can |= p >= (all + 1) / 2; } if(can) { l = md + 1; ans = md; } else { r = md - 1; } } mx = max(mx, ans); l = 1, r = mp[3], ans = 1; while(l <= r) { int md = (l + r) / 2; bool can = false; for(int i = md - 1; i < idx[3].size(); i++) { int j = idx[3][i]; int k = idx[3][i - md + 1]; int p = pref[j][3] - (k ? pref[k - 1][3] : 0); int others = j - k + 1 - p; int all = p + others; can |= p >= (all + 1) / 2; } if(can) { l = md + 1; ans = md; } else { r = md - 1; } } mx = max(mx, ans); l = 1, r = mp[2], ans = 1; while(l <= r) { int md = (l + r) / 2; bool can = false; for(int i = md - 1; i < idx[2].size(); i++) { int j = idx[2][i]; int k = idx[2][i - md + 1]; int p = pref[j][2] - (k ? pref[k - 1][2] : 0); int others = j - k + 1 - p; int all = p + others; can |= p >= (all + 1) / 2; } if(can) { l = md + 1; ans = md; } else { r = md - 1; } } mx = max(mx, ans); // the answer for 2 needs more, but let's submit this return mx; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...