結果

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

ソースコード

diff #
raw source code 

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N = 100000,Q = 100000;
    cin >> N >> Q;
    string s(N,'w');
    cin >> s;
    vector<int> WA(N);
    for(int i=0; i<N; i++){
        WA.at(i) = s.at(i)=='w'||s.at(i)=='a';
        if(i) WA.at(i) += WA.at(i-1);
    }
    while(Q--){
        long long t = 1,x = 600000; cin >> t >> x;
        long long one = 1,add = 1;
        for(long long i=0; i<t; i++){
            if(one > x) break;
            one += add*5,add *= 2;
        }
        x--;
        long long back = 0;
        int low = -1,high = N-1;
        while(high-low > 1){
            int mid = (high+low)/2;
            __int128_t now = WA.at(mid);
            now *= one;
            now += mid+1-WA.at(mid);
            if(now <= x) low = mid;
            else high = mid;  
        }
        {
            int pos = high;
            char c = s.at(pos);
            if(c == 'w' || c == 'a'){
                long long before = WA.at(pos)-1;
                x -= before*one,x -= pos-before;
                vector<long long> memo(100,1);
                long long on = 6,ad = 2;
                for(long long i=1; ; i++){
                    memo.at(i) = on;
                    on += ad*5,ad *= 2;
                    if(x >= memo.at(i)) continue;
                    auto f = [&](auto f,long long X,char C,long long d) -> void {
                        if(d == 0){cout << C; return;}
                        if(C == 'w'){
                            for(auto c : "warong"){
                                if(c == 'w'){
                                    if(X >= memo.at(d-1)) X -= memo.at(d-1);
                                    else{f(f,X,c,d-1); return;}
                                }
                                else if(c == 'a'){
                                    if(X >= memo.at(d-1)) X -= memo.at(d-1);
                                    else{f(f,X,c,d-1); return;}
                                }
                                else{
                                    if(X == 0){cout << c; return;}
                                    X--;
                                }
                            }
                        }
                        else{
                            for(auto c : "answer"){
                                if(c == 'w'){
                                    if(X >= memo.at(d-1)) X -= memo.at(d-1);
                                    else{f(f,X,c,d-1); return;}
                                }
                                else if(c == 'a'){
                                    if(X >= memo.at(d-1)) X -= memo.at(d-1);
                                    else{f(f,X,c,d-1); return;}
                                }
                                else{
                                    if(X == 0){cout << c; return;}
                                    X--;
                                }
                            }
                        }
                    };
                    f(f,x,c,i); break;
                }
            }
            else cout << c; 
        }
    }
    cout << endl;
}
0