QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#679870 | #6812. Draw a triangle | lllei# | WA | 21ms | 3656kb | C++20 | 1.4kb | 2024-10-26 18:59:08 | 2024-10-26 18:59:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
template<typename T>
T exgcd(T a, T b, T &x, T &y){
if (!b){
x = 1, y = 0;
return a;
}
T r = exgcd(b, a % b, y, x);
y -= a / b * x;
return r;
}
// a * x = b (mod m) or b / a (mod m)
array<LL, 2> modequ(LL a, LL b, LL m){
LL x, y;
LL g = exgcd(a, m, x, y);
if (b % g) return {-1, -1};
m /= g, a /= g, b /= g;
x = 1LL * x * b % m;
if (x < 0) x += m;
return {x, m};
}
int sgn(LL x) {
if (x > 0) {
return 1;
} else if (x < 0) {
return -1;
} else {
return 0;
}
}
void solve() {
LL x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (x1 == x2) {
cout << x1 + 1 << ' ' << y1 << '\n';
return;
}
if (y1 == y2) {
cout << x1 << ' ' << y1 + 1 << '\n';
return;
}
LL dx = abs(x2 - x1), dy = abs(y2 - y1);
if (dx == dy) {
cout << x1 + 1 << ' ' << y1 << '\n';
return;
}
LL g = gcd(dx, dy);
dx /= g, dy /= g;
auto [x, m] = modequ(dy, 1LL, dx);
LL t = (y1 + x * (y2 - y1) / (x2 - x1));
cout << x1 + sgn(x2 - x1) * x << ' ' << t << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3648kb
input:
3 1 0 1 4 0 1 0 9 0 0 2 2
output:
2 0 1 1 1 0
result:
ok T=3 (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 21ms
memory: 3656kb
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:
66620474 -33485015 43307637 98029491 -88895354 -3180659 -90319828 20018677 -56783319 84789747 -81798087 90629195 98942862 -939065 -42532258 -57203371 53500176 -30665575 27114943 46989241 -2657436 26865486 40614023 17923572 -47650008 96037810 92954122 -64534754 86508758 -51415065 -82017733 17392605 7...
result:
wrong answer wa on query #2 (test case 2)