結果

問題 No.438 Cwwプログラミング入門
コンテスト
ユーザー ldsyb
提出日時 2026-09-11 23:20:48
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
MLE  
実行時間 -
コード長 3,046 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,064 ms
コンパイル使用メモリ 380,524 KB
実行使用メモリ 1,307,108 KB
最終ジャッジ日時 2026-09-11 23:22:12
合計ジャッジ時間 9,646 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 MLE * 2 -- * 95
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif

pair<int64_t, pair<int64_t, int64_t>> ext_gcd(int64_t x, int64_t y) {
    if (y == 0) {
        return {x, {1, 0}};
    }

    auto [g, p] = ext_gcd(y, x % y);
    auto [u, v] = p;

    // g == u * y + v * (x % y)
    //   == u * y + v * (x - x / y * y)
    //   == u * y + v * x - x / y * y * v
    //   == v * x + (u - x / y * v) * y

    int64_t nu = v, nv = u - x / y * v;

    return {g, {nu, nv}};
}

int main() {
    int64_t x, y, z;
    cin >> x >> y >> z;

    auto Cww = [&](string s) -> int64_t {
        if (10000 < s.size()) {
            cout << "ERROR too long" << endl;
            exit(0);
        }
        stack<int64_t> st;
        for (auto &&c : s) {
            if (c == 'c') {
                st.push(x);
            } else if (c == 'w') {
                st.push(y);
            } else if (c == 'C') {
                if (st.size() < 2) {
                    cout << "ERROR in " << c << endl;
                    exit(0);
                }
                auto a = st.top();
                st.pop();
                auto b = st.top();
                st.pop();
                st.push(a + b);
            } else if (c == 'W') {
                if (st.size() < 2) {
                    cout << "ERROR in " << c << endl;
                    exit(0);
                }
                auto a = st.top();
                st.pop();
                auto b = st.top();
                st.pop();
                st.push(a - b);
            }
        }
        if (st.empty()) {
            cout << "ERROR stack is empty" << endl;
            exit(0);
        }
        return st.top();
    };

    auto [g, p] = ext_gcd(x, y);
    auto [u, v] = p;

    u *= z / g;
    v *= z / g;

    if (g == 0) {
        if (z == 0) {
            cout << "ccW" << endl;
            return 0;
        }

        cout << "NO" << endl;
        return 0;
    }

    if (z % g != 0) {
        cout << "NO" << endl;
        return 0;
    }

    string ans = "";

    if (0 <= u) {
        for (int64_t i = 0; i < u; i++) {
            ans += 'c';
        }
        for (int64_t i = 0; i < u - 1; i++) {
            ans += 'C';
        }
    } else {
        for (int64_t i = 0; i < -u + 2; i++) {
            ans += 'c';
        }
        for (int64_t i = 0; i < -u + 1; i++) {
            ans += 'W';
        }
    }

    if (0 <= v) {
        for (int64_t i = 0; i < v; i++) {
            ans += 'w';
        }
        for (int64_t i = 0; i < v - 1; i++) {
            ans += 'C';
        }
    } else {
        for (int64_t i = 0; i < -v + 2; i++) {
            ans += 'w';
        }
        for (int64_t i = 0; i < -v + 1; i++) {
            ans += 'W';
        }
    }

    if (u != 0 && v != 0) {
        ans += 'C';
    }

    if (10000 < ans.size()) {
        cout << "NO" << endl;
        return 0;
    }

    cout << ans << endl;

    cerr << Cww(ans) << endl;

    return 0;
}
0