結果
問題 |
No.3244 Range Multiple of 8 Query
|
ユーザー |
![]() |
提出日時 | 2025-08-25 07:46:36 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4,162 ms / 5,000 ms |
コード長 | 3,957 bytes |
コンパイル時間 | 3,419 ms |
コンパイル使用メモリ | 290,384 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-25 07:47:52 |
合計ジャッジ時間 | 65,213 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, Q; cin >> N >> Q; string S_str; cin >> S_str; vector<int> S(N); for (int i = 0; i < N; i++) { S[i] = S_str[i] - '0'; } vector<vector<int>> L(10); for (int i = 0; i < N; i++) { L[S[i]].push_back(i); } vector<array<int, 3>> LIST; for (int i = 0; i < 125; i++) { int x = 8 * i; string s = to_string(x); while (s.size() < 3) s = "0" + s; if (s.find('0') != string::npos) continue; array<int, 3> arr; for (int j = 0; j < 3; j++) arr[j] = s[j] - '0'; LIST.push_back(arr); } while (Q--) { int l0, r; cin >> l0 >> r; if (l0 == r) { if (S[l0 - 1] == 8) { cout << 0 << "\n"; } else { cout << -1 << "\n"; } continue; } if (r == l0 + 1) { int x = S[l0 - 1] * 10 + S[l0]; int y = S[l0 - 1] + S[l0] * 10; if (x % 8 == 0) { cout << 0 << "\n"; } else if (y % 8 == 0) { cout << 1 << "\n"; } else { cout << -1 << "\n"; } continue; } long long ANS = (1LL << 60); vector<vector<int>> X(10); for (int j = 0; j < 10; j++) { auto it = upper_bound(L[j].begin(), L[j].end(), r - 1); if (it != L[j].begin()) { int c = *(--it); X[j].push_back(c); } else continue; it = upper_bound(L[j].begin(), L[j].end(), X[j].back() - 1); if (it != L[j].begin()) { int c = *(--it); X[j].push_back(c); } else continue; it = upper_bound(L[j].begin(), L[j].end(), X[j].back() - 1); if (it != L[j].begin()) { int c = *(--it); X[j].push_back(c); } else continue; } for (auto &l : LIST) { vector<int> A; if ((int)X[l[2]].size() >= 1) { A.push_back(X[l[2]][0]); } else continue; if (l[2] != l[1]) { if ((int)X[l[1]].size() >= 1) { A.push_back(X[l[1]][0]); } else continue; } else { if ((int)X[l[1]].size() >= 2) { A.push_back(X[l[1]][1]); } else continue; } if (l[0] == l[1] && l[1] == l[2]) { if ((int)X[l[0]].size() >= 3) { A.push_back(X[l[0]][2]); } else continue; } else if (l[0] == l[1]) { if ((int)X[l[0]].size() >= 2) { A.push_back(X[l[0]][1]); } else continue; } else if (l[0] == l[2]) { if ((int)X[l[0]].size() >= 2) { A.push_back(X[l[0]][1]); } else continue; } else { if ((int)X[l[0]].size() >= 1) { A.push_back(X[l[0]][0]); } else continue; } bool flag = false; for (int a : A) { if (a < l0 - 1) { flag = true; break; } } if (flag) continue; long long score = 0; vector<int> B = A; for (int i = 0; i < 3; i++) { int x = B[i]; score += abs(x - (r - 1 - i)); for (int j = i + 1; j < 3; j++) { if (B[j] > x) B[j]--; } } ANS = min(ANS, score); } if (ANS == (1LL << 60)) { cout << -1 << "\n"; } else { cout << ANS << "\n"; } } return 0; }