結果

問題 No.3320 yiwiwiy
コンテスト
ユーザー のらら
提出日時 2025-10-06 19:07:07
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,649 bytes
コンパイル時間 3,356 ms
コンパイル使用メモリ 183,680 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-10-31 18:55:21
合計ジャッジ時間 30,465 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 11 WA * 61 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
//#define endl "\n";
ll Q, Y, I, W;
ll A, B;

void printYIW(){
    for(int i = 0; i < Y; i++) cout << "y";
    for(int i = 0; i < I; i++) cout << "i";
    for(int i = 0; i < W; i++) cout << "w";
    cout << endl;
}
void printIWIWI(){
    ll cntiw = min(I - 1, W);
    ll restI = I - cntiw;
    ll restW = W - cntiw;
    for(int i = 0; i < Y; i++) cout << "y";
    for(int i = 0; i < cntiw; i++) cout << "iw";
    for(int i = 0; i < I; i++) cout << "i";
    for(int i = 0; i < W; i++) cout << "w";
    cout << endl;
}
void printYIWIY(){
    for(int i = 0; i < Y / 2; i++) cout << "y";
    for(int i = 0; i < I / 2; i++) cout << "i";
    for(int i = 0; i < W; i++) cout << "w";
    for(int i = 0; i < I - I / 2; i++) cout << "i";
    for(int i = 0; i < Y - Y / 2; i++) cout << "y";
    cout << endl;
}
void printX(ll cntiwiwi, ll cntlefti){
    for(int i = 0; i < Y / 2; i++) cout << "y";
    for(int i = 0; i < cntlefti; i++) cout << "i";
    for(int i = 0; i < cntiwiwi; i++) cout << "wi";
    for(int i = 0; i < W - cntiwiwi; i++) cout << "w";
    for(int i = 0; i < I - cntlefti - cntiwiwi; i++) cout << "i";
    for(int i = 0; i < Y - Y / 2; i++) cout << "y";
    cout << endl;
}

int main(){
    cin >> Q;
    for(int q = 1; q <= Q; q++){
        cin >> Y >> I >> W >> A >> B;

        bool isOK_yiwiy = false, isOK_iwiwi = false;
        if(Y >= 2 && I >= 2 && W >= 1) isOK_yiwiy = true;
        if(I >= 3 && W >= 2) isOK_iwiwi = true;
        if(isOK_yiwiy){
            if(isOK_iwiwi){
                //両方作れる
                //iwiwiを含む文字列を三分探索
                auto f2 = [&](ll x, ll y)->__int128{
                    __int128 ret = 0;
                    __int128 left = x;
                    for(int i = 1; i <= x; i++){
                        ret += left;
                        left++;
                    }
                    ret += left * (W - x);
                    ret *= (I - x - (y - 1));
                    return ret;
                };
                auto f = [&](ll x)->pair<__int128, ll>{
                    ll l = 0, r = I - x;
                    while(r - l > 2){
                        ll m1 = (l * 2 + r) / 3;
                        ll m2 = (l + r * 2) / 3;
                        if(f2(m1, x) < f2(m2, x)) l = m1;
                        else r = m2;
                    }
                    __int128 retl = f2(l, x);
                    __int128 retr = f2(r, x);
                    return (retl >= retr ? make_pair(retl, l): make_pair(retr, r));
                };
                ll l = 2, r = min(I - 1, W);
                while(r - l > 2){
                    ll m1 = (l * 2 + r) / 3;
                    ll m2 = (l + r * 2) / 3;
                    if(f(m1).first < f(m2).first) l = m1;
                    else r = m2;
                }
                auto tmpl = f(l);
                auto tmpr = f(r);
                __int128 chkl = f(l).first * (__int128)(Y / 2) * (Y - Y / 2) * A + (__int128)l * B;
                __int128 chkr = f(r).first * (__int128)(Y / 2) * (Y - Y / 2) * A + (__int128)r * B;
                __int128 ret1;
                ll cntiwiwi, cntlefti;
                if(chkl >= chkr){
                    ret1 = chkl;
                    cntiwiwi = l;
                    cntlefti = tmpl.second;
                }else{
                    ret1 = chkr;
                    cntiwiwi = r;
                    cntlefti = tmpr.second;
                }
                //(iwiwiを含む文字列の最大値)<A*(iwiwiを含まない文字列の場合の数)ならprintYIWIY
                __int128 ret2 = (__int128)(Y / 2) * (I / 2) * W * (I - I / 2) * (Y - Y / 2) * A;
                if(ret1 / ret2 < A){
                    printYIWIY();
                    continue;
                }else{
                    //頑張る
                    printX(cntiwiwi, cntlefti);
                    continue;
                }
            }else{
                //yiwiyだけ作れる
                //yyyyyyiiiiiiwwwwwiiiiiiyyyyyyみたいなのがよい
                //左右のyiはできるだけ同じ数がよい
                printYIWIY();
                continue;
            }
        }else{
            if(isOK_iwiwi){
                //iwiwiだけ作れる(貪欲に作る)
                printIWIWI();
                continue;
            }else{
                //0なのでそのまま並べて出力
                printYIW();
                continue;
            }
        }
    }
    return 0;
}
0