結果

問題 No.3244 Range Multiple of 8 Query
ユーザー tnakao0123
提出日時 2025-08-25 15:02:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,049 ms / 5,000 ms
コード長 1,847 bytes
コンパイル時間 661 ms
コンパイル使用メモリ 59,084 KB
実行使用メモリ 26,568 KB
最終ジャッジ日時 2025-08-25 15:03:12
合計ジャッジ時間 19,185 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:33:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   33 |   scanf("%d%d%s", &n, &qn, s);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:48:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   48 |     scanf("%d%d", &l, &r), l--;
      |     ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 3244.cc:  No.3244 Range Multiple of 8 Query - yukicoder
 */

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

/* constant */

const int MAX_N = 288000;
const int INF = 1 << 30;

/* typedef */

using vi = vector<int>;
using vec = int[10];

/* global variables */

char s[MAX_N + 4];
vec cvs[MAX_N], pvs[MAX_N];

/* subroutines */

/* main */

int main() {
  int n, qn;
  scanf("%d%d%s", &n, &qn, s);

  vec pv;
  fill(pv, pv + 10, -1);
  for (int i = 0; i < n; i++) {
    copy(pv, pv + 10, pvs[i]);
    pv[s[i] - '0'] = i;
    copy(pv, pv + 10, cvs[i]);
  }

  vi mv3;
  for (int i = 0; i < 1000; i += 8) mv3.push_back(i);

  while (qn--) {
    int l, r;
    scanf("%d%d", &l, &r), l--;

    if (r - l == 1) {
      int x0 = s[l] - '0';
      if (x0 % 8 == 0) puts("0");
      else puts("-1");
    }
    else if (r - l == 2) {
      int d0 = s[l + 1] - '0', d1 = s[l] - '0';
      int x0 = d0 + d1 * 10, x1 = d1 + d0 * 10;
      if (x0 % 8 == 0) puts("0");
      else if (x1 % 8 == 0) puts("1");
      else puts("-1");
    }
    else { // r - l >= 3
      int minc = INF;
      for (auto mv: mv3) {
	int ds[3] = {mv % 10, (mv / 10) % 10, mv / 100};
	vec cv;
	copy(cvs[r - 1], cvs[r - 1] + 10, cv);

	int c = 0, qs[3];
	for (int i = 0; i < 3; i++) {
	  qs[i] = cv[ds[i]];
	  if (qs[i] < l) { c = INF; break; }
	  cv[ds[i]] = pvs[qs[i]][ds[i]];
	}
	if (c >= INF) continue;

	for (int i = 0, pi = r - 1; i < 3; i++, pi--) {
	  int qi = qs[i];
	  for (int j = i - 1; j >= 0; j--)
	    if (qs[i] > qs[j]) qi--;
	  c += pi - qi;
	}

	minc = min(minc, c);

	if (false) {
	  printf(" %d-%d: ", l, r);
	  for (int i = l; i < r; i++) putchar(s[i]);
	  printf(" mv=%d %d,%d,%d c=%d\n", mv, qs[2], qs[1], qs[0], c);
	}
      }

      printf("%d\n", (minc < INF) ? minc : -1);
    }
  }

  return 0;
}
0