結果

問題 No.3317 ワロングアンサーロングアンサーンスワロンガー
コンテスト
ユーザー のらら
提出日時 2025-08-12 16:42:51
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 271 ms / 2,000 ms
コード長 2,730 bytes
コンパイル時間 3,424 ms
コンパイル使用メモリ 179,432 KB
実行使用メモリ 58,496 KB
最終ジャッジ日時 2025-11-01 09:58:30
合計ジャッジ時間 13,012 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 63
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
//#define endl "\n";
const long long INF = 2000000000000000000;
ll N, Q, dpA[69][7], dpW[69][7];
string S;
string ans = "";
string sw = "warong";
string sa = "answer";

//idx=0:dpA, 1:dpW
void dfs(ll idx, ll num, ll loop){
  if(idx == 0){
    //範囲を絞る
    while(1 < loop && num <= dpA[loop - 1][5]) loop--;
    if(loop == 1){
      ans.push_back(sa[num - 1]);
      return;
    }
    int to = 0;
    while(to < 5 && dpA[loop][to] < num) to++;
    if(to == 0){
      //a
      dfs(0, num, loop - 1);
    }else if(to == 3){
      //w
      dfs(1, num - dpA[loop][2], loop - 1);
    }else{
      ans.push_back(sa[to]);
      return;
    }
  }
  if(idx == 1){
    //範囲を絞る
    while(1 < loop && num <= dpW[loop - 1][5]) loop--;
    if(loop == 1){
      ans.push_back(sw[num - 1]);
      return;
    }
    int to = 0;
    while(to < 5 && dpW[loop][to] < num) to++;
    if(to == 0){
      //w
      dfs(0, num, loop - 1);
    }else if(to == 1){
      //a
      dfs(0, num - dpA[loop][0], loop - 1);
    }else{
      ans.push_back(sw[to]);
      return;
    }
  }
}

int main(){
  cin >> N >> Q;
  cin >> S;
  
  for(int i = 0; i < 6; i++){
    dpA[1][i] = i + 1;
    dpW[1][i] = i + 1;
  }
  ll tasu = 5;
  for(int i = 2; i <= 60; i++){
    dpA[i][0] = min(dpA[i - 1][0] + tasu, INF);
    dpW[i][0] = min(dpW[i - 1][0] + tasu, INF);
    for(int j = 1; j < (int)sw.size(); j++){
      if(sw[j] == 'w' || sw[j] == 'a') dpW[i][j] = min(dpW[i][j - 1] + dpW[i][0], INF);
      else dpW[i][j] = min(dpW[i][j - 1] + 1, INF);
    }
    for(int j = 1; j < (int)sa.size(); j++){
      if(sa[j] == 'w' || sa[j] == 'a') dpA[i][j] = min(dpA[i][j - 1] + dpA[i][0], INF);
      else dpA[i][j] = min(dpA[i][j - 1] + 1, INF);
    }
    if((ll)INF / 2 <= tasu) tasu = INF;
    else tasu *= 2;
  }
  /*for(int i = 1; i <= 60; i++){
    for(int j = 0; j < (int)sw.size(); j++) cout << dpA[i][j] << " ";
    cout << endl;
  }*/
  vector<vector<ll>> sum(69, vector<ll>(N + 1, 0));
  for(int i = 1; i <= 60; i++){
    for(int j = 0; j < N; j++){
      if(S[j] == 'a') sum[i][j + 1] = min(sum[i][j] + dpA[i][5], INF);
      else if(S[j] == 'w') sum[i][j + 1] = min(sum[i][j] + dpW[i][5], INF);
      else sum[i][j + 1] = min(sum[i][j] + 1, INF);
    }
  }
  
  for(int q = 1; q <= Q; q++){
    ll T, X;
    cin >> T >> X;
    ll t = min(T, 60LL);
    ll pos = lower_bound(sum[t].begin(), sum[t].end(), X) - sum[t].begin();
    X -= sum[t][pos - 1];
    if(S[pos - 1] == 'a') dfs(0, X, t);
    else if(S[pos - 1] == 'w') dfs(1, X, t);
    else ans.push_back(S[pos - 1]);
  }
  cout << ans << endl;
  return 0;
}
0