結果
問題 |
No.3244 Range Multiple of 8 Query
|
ユーザー |
![]() |
提出日時 | 2025-08-22 22:20:53 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,799 bytes |
コンパイル時間 | 3,276 ms |
コンパイル使用メモリ | 284,044 KB |
実行使用メモリ | 23,888 KB |
最終ジャッジ日時 | 2025-08-22 22:21:41 |
合計ジャッジ時間 | 44,386 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 19 WA * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; // #include <atcoder/modint> // using namespace atcoder; // using mint = modint998244353; using ll = long long; #define fix(x) fixed << setprecision(x) #define rep(i, n) for(int i = 0; i < n; ++i) #define all(x) (x).begin(),(x).end() template<class T>bool chmin(T&a, const T&b){if(a>b){a=b;return 1;}return 0;} template<class T>bool chmax(T&a, const T&b){if(a<b){a=b;return 1;}return 0;} constexpr ll INFLL = (1LL << 62), MOD = 998244353; constexpr int INF = (1 << 30); int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); vector<vector<int>> z; for(int i=112;i<1000;i+=8){ vector<int> x(3); int y = i; bool f = true; rep(j,3){ if(y%10==0) f = false; x[j] = y%10; y /= 10; } if(f) z.emplace_back(x); } int n,q; string s; cin >> n >> q >> s; vector<vector<int>> pre(n+1, vector<int>(10,-1)); vector<int> y(10,-1); rep(i,n){ y[s[i]-'0'] = i; rep(j,10) pre[i+1][j] = y[j]; } while(q--){ int l,r; cin >> l >> r; --l; int ans = INF; for(auto& v:z){ int upd = 0; vector<int> now(10,r), u(3); rep(i,3){ int x = v[i], k = pre[now[x]][x]; now[x] = k; u[i] = k; if(k<l){ upd = INF; break; } upd += r-1-i-k; } if(u[2]>u[1]) swap(u[2],u[1]), ++upd; if(u[1]>u[0]) swap(u[1],u[0]), ++upd; if(u[2]>u[1]) swap(u[2],u[1]), ++upd; chmin(ans, upd); } if(ans==INF) ans = -1; cout << ans << '\n'; } return 0; }