QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#521615#6812. Draw a triangleTokaiZaopen#WA 16ms3688kbC++171.2kb2024-08-16 13:10:292024-08-16 13:10:30

Judging History

你现在查看的是最新测评结果

  • [2024-08-16 13:10:30]
  • 评测
  • 测评结果:WA
  • 用时:16ms
  • 内存:3688kb
  • [2024-08-16 13:10:29]
  • 提交

answer

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
using i64 = long long;

void EXgcd(i64 a, i64 b, i64& x, i64& y) {
    if (!b)
        x = 1, y = 0;
    else
        EXgcd(b, a % b, y, x), y -= a / b * x;
}

void solve() {
    i64 x0, y0, x1, y1;
    cin >> x0 >> y0 >> x1 >> y1;
    if (x0 == x1) {
        cout << x0 + 1 << ' ' << y0 << endl;
        return;
    }
    if (y0 == y1) {
        cout << x0 << ' ' << y0 + 1 << endl;
        return;
    }
    i64 y = y1 - y0, x = x1 - x0;
    i64 g = gcd(x, y);
    y /= g, x /= g;
    if (x < 0) {
        y = -y;
        x = -x;
    }
    if (x == 1) {
        if (y == 1 || y == -1) {
            cout << x0 << ' ' << y0 - 1 << endl;
            return;
        }
    }
    i64 resx = 1, resy = 0;
    EXgcd(x, y, resy, resx);
    // cout << resx << ' ' << resy << endl;

    if (y % x == 0) {
        resy = y * resx / x - 1;
    } else {
        resy = y * resx / x;
    }
    cout << resx << ' ' << resy << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3688kb

input:

3
1 0 1 4
0 1 0 9
0 0 2 2

output:

2 0
1 1
0 -1

result:

ok T=3 (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 16ms
memory: 3612kb

input:

50000
66620473 -33485015 66620223 -33485265
43307886 98029243 43307636 98028994
-88895230 -3180782 -88895480 -3181030
-90319745 20018595 -90319995 20018348
-56783257 84789686 -56783507 84789440
-81798038 90629147 -81798288 90628902
98942945 -939146 98942695 -939390
-42532151 -57203475 -42532401 -572...

output:

66620473 -33485016
-1 0
-1 0
83 82
62 61
-1 0
-42 -40
107 104
31 30
111 107
-1 0
-91 -86
-21 -19
-77 -72
-18 -16
-17 -15
-47 -43
-103 -95
-14 -12
-79 -72
12 11
119 109
34 31
-87 -78
52 47
-1 0
48 43
37 33
-9 -7
-69 -60
8 7
-121 -105
39 34
53 46
22 19
7 6
-7 -5
27 23
46 39
-109 -91
6 5
-61 -50
-6 -4
...

result:

wrong answer wa on query #2 (test case 2)