結果

問題 No.3299 K-th MMA String
コンテスト
ユーザー The Forsaking
提出日時 2025-10-18 19:11:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 198 ms / 2,000 ms
コード長 1,078 bytes
コンパイル時間 2,165 ms
コンパイル使用メモリ 205,908 KB
実行使用メモリ 11,648 KB
最終ジャッジ日時 2025-10-18 19:11:14
合計ジャッジ時間 4,986 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
const int N = 2000086, MOD = 998244353, INF = 0x3f3f3f3f;
int n, m, w[N];

char ans[N];
multiset<int, greater<int> > st;
set<int> pos = {0};

void add(int x) {
    auto u = pos.upper_bound(x), v = --pos.upper_bound(x);
    if (u != pos.end()) st.erase(st.find(*u - *v)), st.insert(*u - x);
    st.insert(x - *v);
    pos.insert(x);

}
void erase(int x) {
    auto u = pos.upper_bound(x), v = --pos.lower_bound(x);
    if (u != pos.end()) st.erase(st.find(*u - x)), st.insert(*u - *v);
    st.erase(st.find(x - *v));
    pos.erase(x);
}
void ne() {
    for (int i = n; i; i--)
        if (ans[i] == 'M') ans[i] = 'A', add(i);
        else {
            ans[i] = 'M';
            erase(i);
            return;
        }
}

int main() {
    cin >> n >> m;
    fill(ans + 1, ans + n + 1, 'A');
    for (int i = 1; i < n + 1; i++) add(i);
    int t = n - 2;
    while (m) {
        if (*st.begin() > 2) m--;
        if (!m) break;
        ne();
    }
    puts(ans + 1);
    return 0;
}
0