結果

問題 No.2893 Minahoshi (Hard)
コンテスト
ユーザー seekworser
提出日時 2024-07-02 09:11:24
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,906 bytes
コンパイル時間 3,362 ms
コンパイル使用メモリ 265,624 KB
実行使用メモリ 12,700 KB
最終ジャッジ日時 2024-09-13 20:50:46
合計ジャッジ時間 6,984 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other TLE * 1 -- * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const vector<ll> pw2 = {2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048};
int solve() {
    ll n; cin >> n;
    deque<char> ans = {'a', 'b'};
    set<string> rem;
    while (ans.size() < n) {
        ll k = 0, pw2 = 2;
        while (pw2 + k < (int)ans.size()) { k++; pw2 *= 2; }
        if (pw2 + k == (int)ans.size()) {
            ans.push_back(ans[k]);
            for (ll bit=0; bit<(1LL << (k+2)); bit++) {
                string s = "";
                for (size_t i=0; i<k+2; i++) {
                    if (bit & (1LL << i)) s += 'a';
                    else s += 'b';
                }
                rem.insert(s);
            }
            for (size_t i=0; i<=ans.size()-(k+2); i++) {
                string s = "";
                for (size_t j=i; j<i+k+2; j++) s += ans[j];
                rem.erase(s);
            }
            continue;
        }
        auto get_suffix = [&]() -> string {
            string result = "";
            for (size_t j=0; j<k; j++) result += ans[(int)ans.size()-k+j];
            return result;
        };
        string suffix = get_suffix();
        bool flag = false;
        string tmp = "";
        for (auto s : rem) if (s.substr(0, k) == suffix) {
            flag = true;
            tmp = s;
            ans.push_back(s[k]);
            break;
        }
        if (flag) {
            rem.erase(tmp);
            continue;
        }
        string s = *rem.begin();
        rem.erase(rem.begin());
        while (true) {
            ans.push_back(ans[k]);
            ans.pop_front();
            suffix = get_suffix();
            if (s.substr(0, k) == suffix) break;
        }
        ans.push_back(s[k]);
    }
    for (size_t i=0; i<n; i++) cout << ans[i];
    cout << '\n';
    return 0;
}
int main() {
    ll t; cin >> t;
    for (int i=0; i<t; i++) solve();
    return 0;
}
0