QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #815153 | #9880. Origami Warp | ucup-team3695# | WA | 119ms | 3824kb | C++20 | 2.4kb | 2024-12-15 05:50:37 | 2024-12-15 05:50:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
namespace cr = chrono;
namespace rg = ranges;
namespace vw = views;
typedef long long ll;
void normalize_diag(ll &x, ll &y, ll g, bool odd, bool even)
{
if ((x %= 2 * g) < 0)
x += 2 * g;
if ((y %= 2 * g) < 0)
y += 2 * g;
if (x > g)
x = 2 * g - x;
if (y > g)
y = 2 * g - y;
if (odd && x + y > g)
tie(x, y) = pair{g - y, g - x};
if (even && x > y)
tie(x, y) = pair{y, x};
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
int T;
cin >> T;
vector<ll> diags;
diags.reserve(2000);
while (T--)
{
diags.clear();
int n, q;
cin >> n;
ll gx = 0, gy = 0, gd = 0;
bool non_cent = false, irrat = false, diag = false;
while (n--)
{
ll a, b, c, d;
cin >> a >> b >> c >> d;
ll dx = c - a, dy = d - b, cp = dy * a - dx * b;
bool h = dy == 0, v = dx == 0, d1 = dx == dy, d2 = dx == -dy, di = d1 || d2, rat = h || v || di;
non_cent |= cp != 0;
irrat |= !rat;
diag |= di;
if (h)
gx = gcd(gx, b);
else if (v)
gy = gcd(gy, a);
else if (d1)
{
gd = gcd(gd, a - b);
diags.push_back(abs(a - b));
}
else if (d2)
{
gd = gcd(gd, a + b);
diags.push_back(abs(a + b));
}
}
gd = gcd(gcd(gx, gy), gd);
bool dodd = false, deven = false;
if (gx == 0)
gx = 1'000'000'000;
if (gy == 0)
gy = 1'000'000'000;
if (gd == 0)
gd = 1'000'000'000;
for (int d : diags)
(d % (2 * gd) ? dodd : deven) = true;
// cerr << ' ' << gx << ' ' << gy << ' ' << gd << ' ' << non_cent << ' ' << irrat << ' ' << diag << ' ' << dodd
// << ' ' << deven << endl;
cin >> q;
while (q--)
{
ll a, b, c, d;
cin >> a >> b >> c >> d;
ll r1 = a * a + b * b, r2 = c * c + d * d;
if (!non_cent && r1 != r2)
cout << "No\n";
else if (irrat)
cout << "Yes\n";
else if (diag)
{
normalize_diag(a, b, gd, dodd, deven);
normalize_diag(c, d, gd, dodd, deven);
cout << (tie(a, b) == tie(c, d) ? "Yes\n" : "No\n");
}
else if (gx == 0 ? a != c : (c - a) % gx != 0)
cout << "No\n";
else if (gy == 0 ? b != d : (d - b) % gy != 0)
cout << "No\n";
else
cout << "Yes\n";
}
}
}
/*
2
3
0 0 1 0
0 0 0 1
0 2 2 0
4
1 0 2 3
1 -2 -1 2
1 1 -1 0
3 3 3 3
3
0 0 1 0
0 0 0 1
-2 1 2 3
2
2 1 -1 5
-1 -1 3 3
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3780kb
input:
2 3 0 0 1 0 0 0 0 1 0 2 2 0 4 1 0 2 3 1 -2 -1 2 1 1 -1 0 3 3 3 3 3 0 0 1 0 0 0 0 1 -2 1 2 3 2 2 1 -1 5 -1 -1 3 3
output:
Yes Yes No Yes Yes Yes
result:
ok 6 token(s): yes count is 5, no count is 1
Test #2:
score: 0
Accepted
time: 5ms
memory: 3784kb
input:
10 550 0 0 1 0 0 0 0 1 1070451 -76747419 -475756 34109964 39212129 -40187389 32082651 -32880591 -42770825 49053520 -51324990 58864224 301020 -10533714 602040 -21067428 -55137616 74952624 -24122707 32791773 1629975 -29851650 -478126 8756484 80523100 20960200 -77302176 -20121792 -64028006 61179727 -18...
output:
Yes No No Yes Yes No Yes No Yes No No Yes Yes Yes Yes Yes No Yes No No Yes Yes Yes No Yes No No Yes Yes Yes Yes No Yes No No No No No Yes Yes No No No Yes Yes Yes No No No No No No Yes Yes Yes Yes Yes No No Yes Yes Yes No Yes Yes Yes Yes No Yes No Yes Yes Yes No No Yes Yes Yes No No No Yes No Yes Ye...
result:
ok 12244 token(s): yes count is 6128, no count is 6116
Test #3:
score: 0
Accepted
time: 107ms
memory: 3600kb
input:
100 2000 0 0 1 0 0 0 0 1 -84998108 27087723 -78459792 25004052 -63732795 -93286980 29741971 43533924 88160702 10753904 -94457895 -11522040 -57759240 -99131840 25991658 44609328 -35408095 31386545 -92061047 81605017 21178080 37382229 32943680 58150134 -57187533 84956404 -17596164 26140432 38432164 17...
output:
No No No Yes Yes Yes No Yes No No Yes No No No Yes No No Yes No Yes No No No No No No Yes No Yes No Yes Yes Yes Yes No No No Yes Yes No Yes Yes Yes Yes Yes No Yes No Yes No Yes Yes No Yes No Yes Yes No No Yes Yes Yes Yes No No No Yes No No No Yes Yes No No No No No No No No No No No No Yes Yes Yes N...
result:
ok 200000 token(s): yes count is 100141, no count is 99859
Test #4:
score: 0
Accepted
time: 62ms
memory: 3520kb
input:
90 1025 0 0 1 0 0 0 0 1 -8716657 -748858 12990792 -22456307 -13593063 -23283552 -46628353 -23283552 93002789 28574481 93002789 78693002 -16042487 47828662 -30013237 61799412 43359811 68260568 43359811 -75987953 -94388305 52022201 -94388305 8537759 -6363687 -1383673 -6363687 -20211179 -29739675 -2602...
output:
Yes No No No Yes No Yes Yes No Yes No No No No No No No No Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes No No No No Yes Yes Yes No No No Yes Yes Yes No No No No Yes Yes Yes No No Yes Yes No No Yes Yes Yes No Yes No Yes Yes Yes Yes Yes Yes No No Yes Yes No No Yes No Yes No N...
result:
ok 111911 token(s): yes count is 30198, no count is 81713
Test #5:
score: 0
Accepted
time: 46ms
memory: 3520kb
input:
60 1827 0 0 1 0 0 0 0 1 -17538300 -17990820 -3024627 -3477147 1931426 28295794 -7230316 37457536 -50091040 -61102720 -50091040 -81287891 -8748721 7610399 -3122974 13236146 -11031224 10681644 26710340 -27059920 24141834 -4020934 30472616 -10351716 -34145900 53640301 -34145900 50102047 -9267760 282286...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No Yes Yes No No No No Yes No No No No No No No No No No No No No No No No No No No Yes No No No No No Yes No No No No No No No No No No No No Yes Ye...
result:
ok 72683 token(s): yes count is 7452, no count is 65231
Test #6:
score: 0
Accepted
time: 47ms
memory: 3628kb
input:
60 1997 0 0 1 0 0 0 0 1 69327545 -42290317 69327545 63981221 -58631846 -15683378 -58631846 18914662 4797598 12519123 -29048979 46365700 9216180 2556055 20722330 -8950095 -36543647 35024712 -35771895 35024712 -10489112 91685408 -10489112 -57484395 6794531 26436588 6794531 -20764239 -26423402 -4976896...
output:
Yes No No Yes Yes No No Yes Yes Yes No No Yes No Yes No No Yes No No Yes No Yes No No No No No Yes No Yes Yes No No Yes No No No No Yes No No No No No Yes Yes Yes No No Yes Yes No No No Yes Yes Yes No Yes Yes No Yes No Yes No Yes No No Yes No No No Yes No No No No Yes No No No No No No Yes Yes Yes N...
result:
ok 79849 token(s): yes count is 8192, no count is 71657
Test #7:
score: 0
Accepted
time: 39ms
memory: 3824kb
input:
60 807 0 0 1 0 0 0 0 1 69990110 52698324 58640751 52698324 -6015050 2800994 -4061102 4754942 67806960 -10866065 67806960 78717943 -66237090 -99083936 83175963 -99083936 -89057656 -95080370 64126205 -95080370 -74320306 14980336 61936095 14980336 -4691148 24838238 -13069432 33216522 -44184536 34829110...
output:
Yes Yes Yes Yes No No No No Yes No Yes No No Yes No No No No No No No Yes Yes No No No No No No No Yes No No Yes No No No No No No Yes No No No Yes Yes No Yes No No No Yes No No Yes No No No No No Yes Yes No Yes No No No Yes No No No No Yes No No No No No Yes No No Yes No No Yes Yes Yes No Yes No No...
result:
ok 71776 token(s): yes count is 21769, no count is 50007
Test #8:
score: 0
Accepted
time: 35ms
memory: 3496kb
input:
60 1891 0 0 1 0 0 0 0 1 -9198393 -8883107 31549745 -49631245 11096271 -8799824 34381579 -8799824 79393665 44942616 5266446 44942616 80038104 59629280 80038104 -73960991 59670664 95699832 59670664 -81538173 -73541249 -26052008 -16573483 -26052008 60296113 60318720 60104916 60318720 46427576 8929327 4...
output:
Yes Yes No No No No No No No No Yes No No No No No No No No No No No No No No No No No Yes Yes No Yes No No No No No No No No No No No No No No No No No No No No No No No No No Yes No No No Yes No No No No No No No No No No No No No No No No No No No Yes No No No Yes Yes No No No No No No Yes No No ...
result:
ok 72035 token(s): yes count is 14238, no count is 57797
Test #9:
score: 0
Accepted
time: 35ms
memory: 3528kb
input:
55 682 0 0 1 0 0 0 0 1 -17023944 6375984 -32126895 21478935 -8975753 -17499359 -25464803 -1010309 -29768060 -42931964 2968852 -10195052 20010198 8113370 21431358 6692210 -10855708 -19806860 -30869619 207051 10554553 1985831 -11026795 23567179 21880938 -5953302 -28304390 -56138630 7753068 -29186348 -...
output:
No No No No No No No No No No No No Yes No No No No No No No No No No No No Yes No No No No No No No No No No No No No No No No No No No No No No Yes No No No Yes Yes No No No No No No No No No Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No ...
result:
ok 69726 token(s): yes count is 15879, no count is 53847
Test #10:
score: 0
Accepted
time: 119ms
memory: 3636kb
input:
100 2000 0 0 1 0 0 0 0 1 11659007 -12317071 21489140 -2486938 -82315139 90329884 -29802604 90329884 53186946 50733878 53186946 41692310 -26440204 65035919 -26440204 -65223934 7444254 -6850298 -10866206 -25160758 23235570 -41755929 -27157227 8636868 38843792 -25255333 51413751 -25255333 -95459342 741...
output:
No Yes No No Yes No Yes No No Yes Yes No Yes No No No No No No No Yes Yes No Yes Yes No No Yes Yes Yes Yes Yes No No No Yes Yes Yes No Yes Yes No No Yes Yes Yes No No No No No No Yes No Yes Yes Yes No Yes No Yes Yes No Yes No No No Yes No Yes No Yes Yes Yes Yes Yes Yes Yes No No No Yes No No Yes Yes...
result:
ok 200000 token(s): yes count is 99988, no count is 100012
Test #11:
score: -100
Wrong Answer
time: 33ms
memory: 3660kb
input:
64 2 0 0 1 0 0 0 0 1 2000 0 0 0 0 0 0 0 1 0 0 0 2 0 0 0 3 0 0 0 4 0 0 1 0 0 0 1 1 0 0 1 2 0 0 1 3 0 0 1 4 0 0 2 0 0 0 2 1 0 0 2 2 0 0 2 3 0 0 2 4 0 0 3 0 0 0 3 1 0 0 3 2 0 0 3 3 0 0 3 4 0 0 4 0 0 0 4 1 0 0 4 2 0 0 4 3 0 0 4 4 0 1 0 0 0 1 0 1 0 1 0 2 0 1 0 3 0 1 0 4 0 1 1 0 0 1 1 1 0 1 1 2 0 1 1 3 0 ...
output:
Yes No No No No No No No No No No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No No No No No No No No...
result:
wrong answer expected YES, found NO [2003rd token]