結果

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

ソースコード

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);

    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 {
                reverse(ALL(str)); x=stoll(str);
                if(x%8==0) cout<<1<<'\n';
                else cout<<-1<<'\n';
            }
            continue;
        }

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

                int right=-(*idx[c].upper_bound(-r));
                if(right==-1 || right<l) {
                    res=INF; break;
                }

                idx[c].erase(-right);
                ch.push_back(right);
                for(int x: ch) if(right>x) right--;

                int goal=r-1-i;
                res+=abs(goal-right);
            }
            chmin(ans,res);

            for(int x: ch) idx[S[x]-'0'].insert(-x);
        }

        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