Submission #951418

#TimeUsernameProblemLanguageResultExecution timeMemory
951418vjudge1Election (BOI18_election)C++17
0 / 100
2 ms856 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 5e5 + 5; const int M = 19; int solve(vector<int> a, int i, int cnt, int bal, vector<int> res) { if (i == a.size()) { int rev_bal = 0; for (int i = res.size() - 1; i; i--) { rev_bal += res[i]; if (rev_bal < 0) return 1e9; } return cnt; } int ans = 1e9; if (a[i] == 1) { res.push_back(1); ans = min(ans, solve(a, i + 1, cnt, bal + 1, res)); } else { ans = min(ans, solve(a, i + 1, cnt + 1, bal, res)); if (bal > 0) { res.push_back(-1); ans = min(ans, solve(a, i + 1, cnt, bal - 1, res)); } } return ans; } int main() { ios::sync_with_stdio(0); cin.tie(0); srand(time(0)); int n = 50; cin >> n; string s; //"TTCTCC"; // for (int i = 0; i < n; i++) { // s += rand() % 2 ? 'C' : 'T'; // } cin >> s; vector<int> a(n + 1); for (int i = 1; i <= n; i++) { char c = s[i - 1]; a[i] = 1 - 2 * (c == 'T'); } vector<int> pre(n + 1), suf(n + 2); for (int i = 1; i <= n; i++) { pre[i] = pre[i - 1] + a[i]; } for (int i = n; i; i--) { suf[i] = suf[i + 1] + a[i]; } vector<int> pos(2 * n + 5, n + 1); vector<vector<int>> nxt(n + 2, vector<int>(M, n + 1)); for (int i = n; i >= 0; i--) { int tar = pre[i] - 1 - (a[i] == 1); nxt[i][0] = pos[tar + n + 2]; pos[pre[i] + n + 2] = i; } for (int j = 1; j < M; j++) { for (int i = 0; i <= n; i++) { nxt[i][j] = nxt[nxt[i][j - 1]][j - 1]; } } pos.assign(2 * n + 5, 0); vector<vector<int>> prev(n + 2, vector<int>(M)); for (int i = 1; i <= n + 1; i++) { int tar = suf[i] - 1 - (a[i] == 1); prev[i][0] = pos[tar + n + 2]; pos[suf[i] + n + 2] = i; } for (int j = 1; j < M; j++) { for (int i = 1; i <= n + 1; i++) { prev[i][j] = prev[prev[i][j - 1]][j - 1]; } } auto get_l_info = [&](int l, int r) -> array<int, 2> { if (a[l] == 1) l = nxt[l][0]; int cnt = 0; for (int i = M - 1; i >= 0; i--) { if (nxt[l][i] <= r) { l = nxt[l][i]; cnt += 1 << i; } } return {l, cnt + (l <= r)}; }; auto get_r_info = [&](int l, int r) -> array<int, 2> { if (a[r] == 1) r = prev[r][0]; int cnt = 0; for (int i = M - 1; i >= 0; i--) { if (prev[r][i] >= l) { r = prev[r][i]; cnt += 1 << i; } } return {r, cnt + (l <= r)}; }; int q = 1; cin >> q; while (q--) { int l = 1, r = n; cin >> l >> r; auto l1 = get_l_info(l, r); auto r1 = get_r_info(l, r); if (l1[0] < r1[0]) { cout << l1[1] + r1[1] << "\n"; continue; } auto l2 = get_l_info(l, min(l1[0], r1[0]) - 1); auto r2 = get_r_info(max(l1[0], r1[0]) + 1, r); int ans = l2[1] + r2[1]; ans += max(l1[1] - l2[1], r1[1] - r2[1]); cout << ans << "\n"; // int ans2 = solve(a, 1, 0, 0, {}); // if (ans != ans2) { // cout << s << "\n"; // cout << l1[0] << " " << l1[1] << " " << r1[0] << " " << r1[1] << "\n"; // cout << l2[0] << " " << l2[1] << " " << r2[0] << " " << r2[1] << "\n"; // cout << ans << " " << ans2 << "\n"; // } } }

Compilation message (stderr)

election.cpp: In function 'int solve(std::vector<int>, int, int, int, std::vector<int>)':
election.cpp:10:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     if (i == a.size()) {
      |         ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...