#809618 (C++17) No.2104 Multiply-Add

提出ソース

結果

問題	No.2104 Multiply-Add
ユーザー	sortreew
提出日時	2022-10-21 22:48:05
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	7 ms / 2,000 ms
コード長	6,010 bytes
コンパイル時間	2,223 ms
コンパイル使用メモリ	209,316 KB
実行使用メモリ	17,088 KB
最終ジャッジ日時	2024-07-01 07:13:24
合計ジャッジ時間	3,789 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	6 ms 15,680 KB
testcase_01	AC	7 ms 16,072 KB
testcase_02	AC	6 ms 15,428 KB
testcase_03	AC	7 ms 17,088 KB
testcase_04	AC	6 ms 16,196 KB
testcase_05	AC	7 ms 16,068 KB
testcase_06	AC	6 ms 15,424 KB
testcase_07	AC	6 ms 15,300 KB
testcase_08	AC	7 ms 15,812 KB
testcase_09	AC	7 ms 15,172 KB
testcase_10	AC	6 ms 15,172 KB
testcase_11	AC	7 ms 16,452 KB
testcase_12	AC	7 ms 16,324 KB
testcase_13	AC	6 ms 15,560 KB
testcase_14	AC	6 ms 16,452 KB
testcase_15	AC	6 ms 16,068 KB
testcase_16	AC	6 ms 15,560 KB
testcase_17	AC	7 ms 15,172 KB
testcase_18	AC	7 ms 16,068 KB
testcase_19	AC	7 ms 15,296 KB
testcase_20	AC	6 ms 15,940 KB
testcase_21	AC	6 ms 15,560 KB
testcase_22	AC	6 ms 16,068 KB
testcase_23	AC	7 ms 15,812 KB
testcase_24	AC	7 ms 15,560 KB
testcase_25	AC	6 ms 15,300 KB
testcase_26	AC	7 ms 15,172 KB
testcase_27	AC	7 ms 15,424 KB
testcase_28	AC	6 ms 15,424 KB
testcase_29	AC	7 ms 16,836 KB
testcase_30	AC	7 ms 15,428 KB
testcase_31	AC	7 ms 15,556 KB
testcase_32	AC	7 ms 15,560 KB
testcase_33	AC	7 ms 15,560 KB
testcase_34	AC	7 ms 15,556 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include "bits/stdc++.h"
#define YES "YES"
#define NO "NO"
#define Yes "Yes"
#define No "No"
#define DEFAULT              \
    LL ans = solve();        \
    if (ans == NONE)         \
    {                        \
    }                        \
    else                     \
    {                        \
        cout << ans << endl; \
    }
#define YESNO three(solve(), (OUT(YES), 1), (OUT(NO), 0))
#define YesNo three(solve(), OUT(Yes), OUT(No))
#define ECHO OUT(solve())
#define three(A, B, C) ((A) ? (B) : (C))
#define FOR(i, a, b) for (LL i = (a); i < (LL)(b); i++)
#define EFOR(i, a, b) for (LL i = (a); i <= (LL)(b); i++)
#define RFOR(i, a, b) for (LL i = (b - 1); i >= (LL)(a); i--)
#define REP(i, b) FOR(i, zero, b)
#define rep REP
#define EREP(i, b) EFOR(i, zero, b)
#define RREP(i, b) RFOR(i, zero, b)
#define ALL(c) c.begin(), c.end()
#define UNIQUE(c) \
    sort(ALL(c)); \
    c.erase(unique(ALL(c)), c.end())
#define MAX(c) (*max_element(ALL(c)))
#define MIN(c) (*min_element(ALL(c)))
#define MP make_pair
#define FI first
#define SE second
#define SI(x) (LL(x.size()))
#define PB push_back
#define DEBUG(a) OUT(a)
#define DEBUG2(a, b) OUT2(a, b)
#define cat cout << __LINE__ << endl
#define OUT(a) cout << (a) << endl
#define OUT2(a, b) cout << (a) << " " << (b) << endl
#define zero 0LL
#define all ALL
#define pb emplace_back
#define eb pb
#define int long long
using namespace std;
template <typename T>
inline void maximize(T &a, T b) { a = max(a, b); }
template <typename T>
inline void minimize(T &a, T b) { a = min(a, b); }
template <typename T>
inline bool middle(T a, T b, T c) { return b <= a && a <= c; }
template <class T>
inline bool MX(T &l, const T &r) { return l < r ? l = r, 1 : 0; }
template <class T>
inline bool MN(T &l, const T &r) { return l > r ? l = r, 1 : 0; }
typedef int LL;
typedef double ld;
typedef int ut;
typedef vector<ut> VI;
typedef vector<VI> VII;
typedef pair<ut, ut> pr;
typedef pair<ut, pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef tuple<int, int, int, int> tapu;
typedef vector<tapu> Vtapu;
typedef priority_queue<pr, Vpr> PQ;
inline void outputVI(VI x)
{
    REP(i, SI(x)) { cout << three(i, " ", "") << x[i]; }
    OUT("");
}
const int SIZE1 = 5e5 + 1000;
const int SIZE2 = 5010;
const int SIZE3 = 430;
const int SIZE = SIZE1;
const int MAPSIZE = 40;
const LL p998 = 998244353;
const LL p107 = 1000000007;
const LL p = p107;
const LL INF = 1LL << 60;
const long double EPS = 1e-7;
const LL NONE = -2;
#define endl "\n"
ut N, M, D, Q, I, S, V, F;
VI edges[SIZE];
LL vals[SIZE], answer = zero;
// LL A[SIZE],B[SIZE],C[SIZE];
bool calced[100][100][100][3][3];
LL dp[100][100][100][3][3];
LL X, Y, K, P;
Vpr ans;
Vpr revans;
void add(LL a, LL b)
{
    ans.pb(a, b);
}
void revadd(LL a, LL b)
{
    revans.pb(a, b);
}

LL revsolve(LL a, LL b)
{
    if (a == 0)
    {
        revadd(1, 1);
        a = b;
    }
    if (b == 0)
    {
        revadd(2, 1);
        b = a;
    }
    LL mini = gcd(abs(a), abs(b));

    while (a != mini or b != mini)
    {
        if (abs(a) < abs(b))
        {
            if (abs(a) / a == abs(b) / b)
            {
                revadd(2, -((abs(b) - 1) / abs(a)));
                b -= (abs(b) - 1) / abs(a) * a;
            }
            else
            {
                revadd(2, +((abs(b) - 1) / abs(a)));
                b += (abs(b) - 1) / abs(a) * a;
            }
        }
        else if (abs(a) > abs(b))
        {
            if (abs(a) / a == abs(b) / b)
            {
                revadd(1, -((abs(a) - 1) / abs(b)));
                a -= (abs(a) - 1) / abs(b) * b;
            }
            else
            {
                revadd(1, +((abs(a) - 1) / abs(b)));
                a += (abs(a) - 1) / abs(b) * b;
            }
        }
        else if (a != mini)
        {
            if (b != mini)
            {
                revadd(1, -2);
            }
            else
            {
                revadd(1, 2);
            }
            a = mini;
        }
        else
        {
            revadd(2, 2);
            b = mini;
        }
    }
    return 0;
}
LL solve()
{
    LL a, b, c, d;
    cin >> a >> b >> c >> d;
    if (a == c and b == d)
        return 0;
    if ((a == 0 and b == 0) or (c == 0 and d == 0))
        return -1;
    if (gcd(abs(a), abs(b)) != gcd(abs(c), abs(d)))
        return -1;

    if (a == 0)
    {
        add(1, 1);
        a = b;
    }
    if (b == 0)
    {
        add(2, 1);
        b = a;
    }
    LL mini = gcd(abs(a), abs(b));

    while (a != mini or b != mini)
    {
        if (abs(a) < abs(b))
        {
            if (abs(a) / a == abs(b) / b)
            {
                add(2, -((abs(b) - 1) / abs(a)));
                b -= (abs(b) - 1) / abs(a) * a;
            }
            else
            {
                add(2, +((abs(b) - 1) / abs(a)));
                b += (abs(b) - 1) / abs(a) * a;
            }
        }
        else if (abs(a) > abs(b))
        {
            if (abs(a) / a == abs(b) / b)
            {
                add(1, -((abs(a) - 1) / abs(b)));
                a -= (abs(a) - 1) / abs(b) * b;
            }
            else
            {
                add(1, +((abs(a) - 1) / abs(b)));
                a += (abs(a) - 1) / abs(b) * b;
            }
        }
        else if (a != mini)
        {
            if (b != mini)
            {
                add(1, -2);
            }
            else
            {
                add(1, 2);
            }
            a = mini;
        }
        else
        {
            add(2, 2);
            b = mini;
        }
    }
    revsolve(c, d);
    return ans.size() + revans.size();
}
signed main()
{

    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    LL T = 1;
    REP(i, T)
    {
        DEFAULT;
    }
    for (auto x : ans)
    {
        cout << x.first << " " << x.second << endl;
    }
    RREP(i, revans.size())
    {
        cout << revans[i].first << " " << -revans[i].second << endl;
    }

    return 0;
}

yukicoder

結果

テストケース

ソースコード