結果

問題 No.2947 Sing a Song
コンテスト
ユーザー Tatsu_mr
提出日時 2024-10-25 21:49:06
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 60 ms / 2,000 ms
コード長 1,680 bytes
コンパイル時間 2,840 ms
コンパイル使用メモリ 247,472 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-25 21:49:12
合計ジャッジ時間 5,857 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define For(i, a, b) for(long long i = a; i < b; i++)
#define rep(i, n) For(i, 0, n)
#define rFor(i, a, b) for(long long i = a; i >= b; i--)
#define ALL(v) (v).begin(), (v).end()
#define rALL(v) (v).rbegin(), (v).rend()
using namespace std;

using lint = long long;
using ld = long double;

int INF = 2000000000;
lint LINF = 1000000000000000000;

long long gcd_array(vector<long long> a) {
    long long ans = a[0];
    for (int i = 0; i < (int)a.size(); i++) {
        ans = gcd(ans, a[i]);
    }
    return ans;
}

// ax + by = gcd(a, b) を満たす (x, y) を求める
// c が gcd(a, b) で割り切れないと、ax + by = c を満たす c は存在しない
// 負の数の場合の処理に注意
long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

pair<lint, lint> f(lint a, lint b, lint c) {
    lint x, y;
    extGCD(a, b, x, y);
    lint g = gcd(a, b);
    x *= c / g;
    y *= c / g;
    lint da = a / g, db = b / g;
    if (y > 0) {
        lint q = y / da;
        x += db * q;
        y -= da * q;
    } else {
        lint q = abs(y) / da + (abs(y) % da != 0);
        x -= db * q;
        y += da * q;
    }
    return {x, y};
}

int main() {
    int n;
    string s, t;
    cin >> n >> s >> t;
    lint a = s.size(), b = t.size();
    rep(i, n) {
        lint c;
        cin >> c;
        auto [x, y] = f(a, b, c);
        rep(_, x) {
            cout << s << " ";
        }
        rep(_, y) {
            cout << t << " ";
        }
        cout << endl;
    }
}
0