Submission #8665350
Source Code Expand
/** * author: tourist * created: 26.11.2019 17:52:04 **/ #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } string s; cin >> s; int low = 1, high = n; while (low < high) { int mid = (low + high + 1) >> 1; vector<int> b(n); for (int i = 0; i < n; i++) { b[i] = (a[i] >= mid); } vector<int> seq(1, 1); for (int i = 1; i < n; i++) { if (b[i] != b[i - 1]) { seq.push_back(1); } else { seq.back() += 1; } } int sz = (int) seq.size(); vector<int> what(sz); for (int i = 0; i < sz; i++) { what[i] = (b[0] + i) % 2; } vector<set<pair<int, int>>> inner(2); vector<int> delta(2, 0); for (int i = 1; i < sz - 1; i++) { inner[what[i]].emplace(seq[i], i); } vector<int> pr(sz + 2); vector<int> ne(sz + 2); for (int i = 0; i < sz + 2; i++) { pr[i] = i - 1; ne[i] = i + 1; } auto Next = [&](int x) { return ne[x + 1] - 1; }; auto Prev = [&](int x) { return pr[x + 1] - 1; }; auto Head = [&]() { return ne[0] - 1; }; auto Tail = [&]() { return pr[sz + 1] - 1; }; auto Remove = [&](int x) { pr[ne[x + 1]] = pr[x + 1]; ne[pr[x + 1]] = ne[x + 1]; }; for (char c : s) { int lft = Head(); int rgt = Tail(); if (lft == rgt) { break; } int u = (c == 'm' ? 0 : 1); delta[u] += 1; delta[u ^ 1] -= 1; if (what[lft] != u) { --seq[lft]; if (seq[lft] == 0) { int to = Next(lft); Remove(lft); if (to == rgt) { break; } inner[u].erase({seq[to], to}); seq[to] += delta[what[to]]; lft = to; } } if (what[rgt] != u) { --seq[rgt]; if (seq[rgt] == 0) { int to = Prev(rgt); Remove(rgt); if (to == lft) { break; } inner[u].erase({seq[to], to}); seq[to] += delta[what[to]]; rgt = to; } } while (!inner[u ^ 1].empty() && inner[u ^ 1].begin()->first + delta[u ^ 1] == 0) { int me = inner[u ^ 1].begin()->second; inner[u ^ 1].erase(inner[u ^ 1].begin()); if (Prev(me) != lft && Next(me) != rgt) { inner[u].erase({seq[Prev(me)], Prev(me)}); inner[u].erase({seq[Next(me)], Next(me)}); seq[Prev(me)] += seq[Next(me)] + delta[u]; inner[u].emplace(seq[Prev(me)], Prev(me)); Remove(me); Remove(Next(me)); } else { if (Prev(me) != lft) { inner[u].erase({seq[Prev(me)], Prev(me)}); seq[Next(me)] += seq[Prev(me)] + delta[u]; Remove(me); Remove(Prev(me)); } else { if (Next(me) != rgt) { inner[u].erase({seq[Next(me)], Next(me)}); seq[Prev(me)] += seq[Next(me)] + delta[u]; Remove(me); Remove(Next(me)); } else { seq[Prev(me)] += seq[Next(me)]; Remove(me); Remove(Next(me)); } } } } } assert(Head() == Tail()); if (what[Head()] == 1) { low = mid; } else { high = mid - 1; } } cout << low << '\n'; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Compression |
User | tourist |
Language | C++14 (GCC 5.4.1) |
Score | 1400 |
Code Size | 3641 Byte |
Status | AC |
Exec Time | 346 ms |
Memory | 4296 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | 800 / 800 | 200 / 200 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt |
subtask1 | sample_2.txt, subtask_1.2_1.txt, subtask_1.2_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
subtask2 | sample_1.txt, subtask_1.2_1.txt, subtask_1.2_2.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt |
All | sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, 2_1.txt, 2_2.txt, sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, subtask_1.2_1.txt, subtask_1.2_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_10.txt, subtask_3_11.txt, subtask_3_12.txt, subtask_3_13.txt, subtask_3_14.txt, subtask_3_15.txt, subtask_3_16.txt, subtask_3_17.txt, subtask_3_18.txt, subtask_3_19.txt, subtask_3_2.txt, subtask_3_20.txt, subtask_3_21.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
2_1.txt | AC | 1 ms | 256 KB |
2_2.txt | AC | 1 ms | 256 KB |
sample_1.txt | AC | 1 ms | 256 KB |
sample_2.txt | AC | 1 ms | 256 KB |
sample_3.txt | AC | 1 ms | 256 KB |
sample_4.txt | AC | 1 ms | 256 KB |
subtask_1.2_1.txt | AC | 1 ms | 256 KB |
subtask_1.2_2.txt | AC | 1 ms | 256 KB |
subtask_1_1.txt | AC | 67 ms | 4296 KB |
subtask_1_10.txt | AC | 68 ms | 4296 KB |
subtask_1_2.txt | AC | 68 ms | 4296 KB |
subtask_1_3.txt | AC | 68 ms | 4296 KB |
subtask_1_4.txt | AC | 60 ms | 3836 KB |
subtask_1_5.txt | AC | 13 ms | 768 KB |
subtask_1_6.txt | AC | 68 ms | 4296 KB |
subtask_1_7.txt | AC | 1 ms | 256 KB |
subtask_1_8.txt | AC | 67 ms | 4296 KB |
subtask_1_9.txt | AC | 67 ms | 4296 KB |
subtask_2_1.txt | AC | 257 ms | 4296 KB |
subtask_2_10.txt | AC | 241 ms | 4296 KB |
subtask_2_2.txt | AC | 120 ms | 4296 KB |
subtask_2_3.txt | AC | 264 ms | 4296 KB |
subtask_2_4.txt | AC | 111 ms | 4296 KB |
subtask_2_5.txt | AC | 1 ms | 256 KB |
subtask_2_6.txt | AC | 1 ms | 256 KB |
subtask_2_7.txt | AC | 1 ms | 256 KB |
subtask_2_8.txt | AC | 266 ms | 4220 KB |
subtask_2_9.txt | AC | 26 ms | 1152 KB |
subtask_3_1.txt | AC | 342 ms | 4296 KB |
subtask_3_10.txt | AC | 215 ms | 4296 KB |
subtask_3_11.txt | AC | 346 ms | 4296 KB |
subtask_3_12.txt | AC | 68 ms | 4296 KB |
subtask_3_13.txt | AC | 71 ms | 4296 KB |
subtask_3_14.txt | AC | 69 ms | 4296 KB |
subtask_3_15.txt | AC | 68 ms | 4296 KB |
subtask_3_16.txt | AC | 68 ms | 4296 KB |
subtask_3_17.txt | AC | 68 ms | 4296 KB |
subtask_3_18.txt | AC | 68 ms | 4296 KB |
subtask_3_19.txt | AC | 68 ms | 4296 KB |
subtask_3_2.txt | AC | 244 ms | 4296 KB |
subtask_3_20.txt | AC | 69 ms | 4296 KB |
subtask_3_21.txt | AC | 69 ms | 4296 KB |
subtask_3_3.txt | AC | 31 ms | 820 KB |
subtask_3_4.txt | AC | 289 ms | 3836 KB |
subtask_3_5.txt | AC | 261 ms | 3480 KB |
subtask_3_6.txt | AC | 287 ms | 4296 KB |
subtask_3_7.txt | AC | 206 ms | 4296 KB |
subtask_3_8.txt | AC | 214 ms | 4296 KB |
subtask_3_9.txt | AC | 119 ms | 4296 KB |