結果

問題 No.3317 ワロングアンサーロングアンサーンスワロンガー
コンテスト
ユーザー のらら
提出日時 2025-08-12 16:25:27
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,800 bytes
コンパイル時間 3,073 ms
コンパイル使用メモリ 177,256 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-10-30 09:42:03
合計ジャッジ時間 14,323 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 55 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

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;
  }*/
  
  for(int q = 1; q <= Q; q++){
    ll T, X;
    cin >> T >> X;
    for(int i = 0; i < (int)S.size(); i++){
      if(S[i] == 'a'){
        if(X <= dpA[min(T, 60LL)][5]){
          //この範囲に求める文字がある
          dfs(0, X, min(T, 60LL));
          break;
        }else{
          X -= dpA[min(T, 60LL)][5];
          continue;
        }
      }
      if(S[i] == 'w'){
        if(X <= dpW[min(T, 60LL)][5]){
          //この範囲に求める文字がある
          dfs(1, X, min(T, 60LL));
          break;
        }else{
          X -= dpW[min(T, 60LL)][5];
          continue;
        }
      }
      X--;
      if(X == 0){
        ans.push_back(S[i]);
        break;
      }
    }
  }
  cout << ans << endl;
  return 0;
}
0