結果

問題 No.3244 Range Multiple of 8 Query
ユーザー テナガザル
提出日時 2025-08-22 23:48:45
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,393 bytes
コンパイル時間 963 ms
コンパイル使用メモリ 104,972 KB
実行使用メモリ 23,844 KB
最終ジャッジ日時 2025-08-22 23:50:32
合計ジャッジ時間 36,813 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 WA * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  vector<vector<int>> id(n, vector<int> (10, -1));
  id[0][s[0] - '0'] = 0;
  for (int i = 1; i < n; ++i)
  {
    id[i] = id[i - 1];
    id[i][s[i] - '0'] = i;
  }
  int nowcnt[10] = {0};
  auto cal = [&](int l, int r, int v) -> int
  {
    int ans = 0;
    for (int i = 0, tmp = v; i < 3; ++i)
    {
      if (tmp % 10 == 0)
      {
        return (1 << 30);
      }
      tmp /= 10;
    }
    int val[3] = {1000000, 1000000, 1000000};
    for (int i = 0; i < 3; ++i)
    {
      int tmp = v % 10, tid = id[r - 1][tmp];
      for (int j = 0; j < nowcnt[tmp]; ++j)
      {
        if (tid <= 0) return (1 << 30);
        tid = id[tid - 1][tmp];
      }
      ++nowcnt[tmp];
      if (tid < l)
      {
        return (1 << 30);
      }
      val[i] = tid;
      for (int j = 0; j < i; ++j)
      {
        if (val[j] < tid) --tid;
      }
      ans += abs(tid - (r - i - 1));
      v /= 10;
    }
    return ans;
  };
  while (q--)
  {
    int l, r;
    cin >> l >> r;
    --l;
    int ans = 1e9;
    for (int i = 14; i < 125; ++i)
    {
      ans = min(ans, cal(l, r, i * 8));
      int v = i * 8;
      while (v > 0)
      {
        nowcnt[v % 10] = 0;
        v /= 10;
      }
    }
    if (ans >= 1e9) ans = -1;
    cout << ans << '\n';
  }
}
0