結果

問題 No.3317 ワロングアンサーロングアンサーンスワロンガー
コンテスト
ユーザー tau1235
提出日時 2025-10-31 23:27:32
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 580 ms / 2,000 ms
コード長 1,370 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,022 ms
コンパイル使用メモリ 291,920 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-11-01 10:01:58
合計ジャッジ時間 19,603 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 63
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;

int main(){
  using ll=long long;
  int n,q;
  string s;
  cin>>n>>q>>s;
  int top=-1;
  for (int i=0;i<n;i++){
    if (s[i]=='w'||s[i]=='a'){
      top=i;
      break;
    }
  }
  vector<pair<ll,ll>> tx(q);
  vector<vector<pair<ll,ll>>> vec(62);
  for (int i=0;i<q;i++){
    ll t,x;
    cin>>t>>x;
    tx[i]={t,x};
    if (t<60) vec[t].push_back({x,i});
  }
  auto f=[&](char c,int t){
    ll len=1;
    if (c=='w'||c=='a') len=(1LL<<t)+(1LL<<(t+2))-4;
    return len;
  };
  vector<int> pre(q,-1);
  for (int k=1;k<60;k++){
    sort(vec[k].begin(),vec[k].end());
    int j=0;
    ll sum=0;
    for (int i=0;i<n;i++){
      ll prev=sum;
      sum+=f(s[i],k);
      while (j<vec[k].size()&&sum>=vec[k][j].first){
        pre[vec[k][j].second]=i;
        tx[vec[k][j].second].second-=prev;
        j++;
      }
    }
  }
  for (int k=0;k<q;k++){
    auto [t,x]=tx[k];
    string now;
    if (t<60){
      now+=s[pre[k]];
    }
    else{
      now+=s[top];
      x-=top;
      t=60;
    }
    while (t){
      for (char c:now){
        ll len=f(c,t);
        if (x>len) x-=len;
        else{
          string next;
          next+=c;
          if (c=='w') next="warong";
          if (c=='a') next="answer";
          swap(now,next);
          break;
        }
      }
      t--;
    }
    cout<<now[x-1];
  }
  cout<<endl;
}
0