結果

問題 No.3244 Range Multiple of 8 Query
コンテスト
ユーザー Today03
提出日時 2025-08-23 15:08:26
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,912 bytes
コンパイル時間 2,934 ms
コンパイル使用メモリ 294,888 KB
実行使用メモリ 37,308 KB
最終ジャッジ日時 2025-08-23 15:09:27
合計ジャッジ時間 54,445 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 27 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
    下3桁を8の倍数にしたい。
    時間制約的に、1000以下の8の倍数全探索は行けそう。

    下3桁を固定する。下3桁の3文字をその位置に持ってくるための最小操作回数を求めたい。
    各文字が存在する最も右の位置を見て、その距離の総和を足せば良い？
*/

#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for(ll i=0; i<(ll)(n); i++)

template<typename T> bool chmax(T& a, T b) { return a<b ? a=b, true : false; }
template<typename T> bool chmin(T& a, T b) { return a>b ? a=b, true : false; }
using ll=long long; const int INF=1e9+10; const ll INFL=4e18;
using VI=vector<int>; using VVI=vector<VI>; using VL=vector<ll>; using VVL=vector<VL>;
using PL=pair<ll,ll>; using VP=vector<PL>; using WG=vector<vector<pair<int,ll>>>;

#ifdef LOCAL
#include "./debug.hpp"
#else
#define debug(...)
#define print_line
#endif


//----------------------------------------------------------

void solve() {
    ll N,Q; cin>>N>>Q;
    string S; cin>>S;

    //8の倍数
    vector<string> eights;
    for(ll t=0; t<1000; t+=8) {
        string s=to_string(t);
        while(s.size()<3) s="0"+s;
        reverse(ALL(s));
        if(count(ALL(s),'0')>0) continue;
        eights.push_back(s);
    }

    vector<set<int>> idx(10);
    REP(i,N) idx[S[i]-'0'].insert(-i);
    REP(i,10) idx[i].insert(1);

    //leftmost[i][j] := iより左の、最も右にあるjの位置
    VVI leftmost(N+1,VI(10,-1));
    REP(i,N) {
        REP(j,10) {
            if(j==S[i]-'0') leftmost[i+1][j]=i;
            else leftmost[i+1][j]=leftmost[i][j];
        }
    }

    while(Q--) {
        ll l,r; cin>>l>>r; l--;

        if(r-l==1) {
            if(S[l]=='8') cout<<0<<'\n';
            else cout<<-1<<'\n';
            continue;
        }
        else if(r-l==2) {
            string str=S.substr(l,2);
            ll x=stoll(str);
            if(x%8==0) cout<<0<<'\n';
            else {
                if(x%8==0) cout<<1<<'\n';
                else cout<<-1<<'\n';
            }
            continue;
        }

        ll ans=INF;
        for(auto s: eights) {
            ll res=0;
            VI ch(10,r), idxs;
            REP(i,3) {
                int c=s[i]-'0';

                int right=leftmost[ch[c]][c];
                if(right==-1 || right<l) {
                    res=INF; break;
                }
                ch[c]=right;

                int dist=(r-1-i)-right;

                for(int ii: idxs) if(ii<right) dist++;
                idxs.push_back(right);

                res+=dist;
            }
            chmin(ans,res); debug(s,res,ch);
        }

        if(ans==INF) ans=-1;
        cout<<ans<<'\n';
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    //cout<<fixed<<setprecision(15);
    int T=1; //cin>>T;
    while(T--) solve();
}
0