QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#512757 | #8708. Portal | AA_Surely# | 1 | 56ms | 10884kb | C++23 | 3.5kb | 2024-08-10 15:40:01 | 2024-08-10 15:40:01 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define FOR(i, x, n) for(int i = x; i < n; i++)
#define F0R(i, n) FOR(i, 0, n)
#define ROF(i, x, n) for(int i = n - 1; i >= x; i--)
#define R0F(i, n) ROF(i, 0, n)
#define WTF cout << "WTF" << endl
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define F first
#define S second
#define PB push_back
#define EP emplace_back
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;
typedef complex<LD> Point;
const int N = 2e5 + 7;
const int INF = 1e9 + 7;
const int LOG = 22;
const int A = 26;
const int SQ = 320;
const int MOD = 1e9 + 7;
LL n;
LL ns[N][2], dists[N][2];
map<LL, vector<LL>> x, y;
LL allx, ally;
int main() {
IOS;
cin >> n;
if (n <= 2) {
cout << -1 << endl;
return 0;
}
F0R(i, n) {
cin >> ns[i][0] >> ns[i][1];
x[ ns[i][0] ].PB(ns[i][1]);
y[ ns[i][1] ].PB(ns[i][0]);
}
FOR(i, 1, n) {
allx = __gcd(allx, abs(ns[i][0] - ns[i - 1][0]));
ally = __gcd(ally, abs(ns[i][1] - ns[i - 1][1]));
}
LL xs_gc = 0, ys_gc = 0;
F0R(_, 3) {
VPLL dists;
FOR(i, 1, n) {
PLL x;
x.F = ns[i][0] - ns[0][0];
x.S = ns[i][1] - ns[0][1];
if (x.F != 0 && x.S != 0) {
dists.PB(x);
}
else if (x.F == 0) {
ys_gc = __gcd(ys_gc, abs(x.S));
}
else if (x.S == 0) {
xs_gc = __gcd(xs_gc, abs(x.F));
}
}
FOR(i, 2, dists.size()) {
if (dists[i - 1].F < 0) {
dists[i - 1].F *= -1;
dists[i - 1].S *= -1;
}
if (dists[i].F < 0) {
dists[i].F *= -1;
dists[i].S *= -1;
}
int g = __gcd(dists[i].F, dists[i - 1].F);
ys_gc = __gcd(1ll * ys_gc, abs(1ll * dists[i].S * dists[i - 1].F / g - 1ll * dists[i - 1].S * dists[i].F / g));
if (dists[i - 1].S < 0) {
dists[i - 1].S *= -1;
dists[i - 1].F *= -1;
}
if (dists[i].S < 0) {
dists[i].S *= -1;
dists[i].F *= -1;
}
g = __gcd(dists[i].S, dists[i - 1].S);
xs_gc = __gcd(1ll * xs_gc, abs(1ll * dists[i].F * dists[i - 1].S / g - 1ll * dists[i - 1].F * dists[i].S / g));
}
if (_ == 0) {
FOR(i, 1, n) if (ns[i][0] != ns[0][0]) {
swap(ns[i], ns[0]);
}
}
if (_ == 2) {
FOR(i, 1, n) if (ns[i][1] != ns[0][1]) {
swap(ns[i], ns[0]);
}
}
}
for(auto &[a, b] : x) {
LL gc = 0;
FOR(i, 1, b.size())
gc = __gcd(abs(b[i - 1] - b[i]), gc);
ys_gc = __gcd(ys_gc, gc);
if (b.size() >= 2) xs_gc = __gcd(xs_gc, allx);
}
for(auto &[a, b] : y) {
LL gc = 0;
FOR(i, 1, b.size())
gc = __gcd(abs(b[i - 1] - b[i]), gc);
xs_gc = __gcd(xs_gc, gc);
if (b.size() >= 2) ys_gc = __gcd(ys_gc, allx);
}
if (ys_gc == 0 || xs_gc == 0) {
cout << -1 << endl;
return 0;
}
cout << 1ll * ys_gc * xs_gc << endl;
}
詳細信息
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 0ms
memory: 3600kb
input:
1 1 -1
output:
-1
result:
ok single line: '-1'
Test #2:
score: 1
Accepted
time: 0ms
memory: 3604kb
input:
2 -455833 -283524 427847 159281
output:
-1
result:
ok single line: '-1'
Test #3:
score: 1
Accepted
time: 0ms
memory: 3700kb
input:
2 52420 -46322 -192914 87067
output:
-1
result:
ok single line: '-1'
Test #4:
score: 1
Accepted
time: 0ms
memory: 3616kb
input:
2 52446 -20773 179773 174566
output:
-1
result:
ok single line: '-1'
Test #5:
score: 1
Accepted
time: 0ms
memory: 3596kb
input:
2 -229012 -260770 -174790 -69382
output:
-1
result:
ok single line: '-1'
Test #6:
score: 1
Accepted
time: 0ms
memory: 3592kb
input:
2 -127294 418312 211124 37002
output:
-1
result:
ok single line: '-1'
Test #7:
score: 1
Accepted
time: 0ms
memory: 3776kb
input:
2 -129173 516840 46821 -187136
output:
-1
result:
ok single line: '-1'
Test #8:
score: 1
Accepted
time: 0ms
memory: 3532kb
input:
2 -90088 -7423 234488 19625
output:
-1
result:
ok single line: '-1'
Test #9:
score: 1
Accepted
time: 0ms
memory: 3588kb
input:
2 -48105 256695 15135 -80585
output:
-1
result:
ok single line: '-1'
Test #10:
score: 1
Accepted
time: 0ms
memory: 3524kb
input:
2 -251318 79061 182792 -129183
output:
-1
result:
ok single line: '-1'
Test #11:
score: 1
Accepted
time: 0ms
memory: 3824kb
input:
2 784850 417677 -217245 -460999
output:
-1
result:
ok single line: '-1'
Test #12:
score: 1
Accepted
time: 0ms
memory: 3616kb
input:
2 31270 410692 713271 917276
output:
-1
result:
ok single line: '-1'
Test #13:
score: 1
Accepted
time: 0ms
memory: 3788kb
input:
1 230862 -785444
output:
-1
result:
ok single line: '-1'
Test #14:
score: 1
Accepted
time: 0ms
memory: 3600kb
input:
2 222814 -279784 -73657 59849
output:
-1
result:
ok single line: '-1'
Test #15:
score: 1
Accepted
time: 0ms
memory: 3464kb
input:
2 72171 -104186 201480 105502
output:
-1
result:
ok single line: '-1'
Test #16:
score: 1
Accepted
time: 0ms
memory: 3616kb
input:
2 -17727 -27151 69235 15029
output:
-1
result:
ok single line: '-1'
Test #17:
score: 1
Accepted
time: 0ms
memory: 3544kb
input:
2 -44049 96618 173806 -21489
output:
-1
result:
ok single line: '-1'
Test #18:
score: 1
Accepted
time: 0ms
memory: 3532kb
input:
2 -81268 -53452 329866 -163275
output:
-1
result:
ok single line: '-1'
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #19:
score: 10
Accepted
time: 1ms
memory: 5876kb
input:
3 1 1 1 3 3 2
output:
4
result:
ok single line: '4'
Test #20:
score: 0
Wrong Answer
time: 1ms
memory: 5532kb
input:
3 123741 -122828 207774 110184 -33847 97305
output:
-1
result:
wrong answer 1st lines differ - expected: '55218331445', found: '-1'
Subtask #3:
score: 0
Wrong Answer
Test #40:
score: 0
Wrong Answer
time: 56ms
memory: 10884kb
input:
99840 -359536 735499 -710626 400619 -468266 -282389 -192706 43659 204034 -543669 -100576 -749013 -118006 -283125 -341276 405771 560934 835595 -923936 506603 239724 956299 -680746 -737237 286204 982795 -847576 -282389 -949666 986475 996684 -429589 672984 -133717 140954 696491 -879116 -442837 985064 7...
output:
1660
result:
wrong answer 1st lines differ - expected: '610880', found: '1660'
Subtask #4:
score: 0
Wrong Answer
Test #59:
score: 29
Accepted
time: 0ms
memory: 5636kb
input:
5 0 0 1 0 -1 0 0 1 0 -1
output:
1
result:
ok single line: '1'
Test #60:
score: 29
Accepted
time: 1ms
memory: 5808kb
input:
100 -30 -13 -22 -19 32 9 -18 -11 50 19 16 5 -50 -17 -46 -21 10 -1 -56 -19 2 -11 -24 -15 -4 -11 -8 -11 4 7 -8 -5 34 9 18 7 20 1 -12 -11 -30 -23 -42 -13 -24 -3 16 11 -16 -7 -24 -21 2 -9 28 11 6 -9 -22 -11 4 -7 28 7 -36 -15 -20 -21 4 11 -8 5 20 5 30 21 58 19 4 -1 -46 -19 -6 3 2 11 46 15 18 -1 -24 -7 -2...
output:
4
result:
ok single line: '4'
Test #61:
score: 29
Accepted
time: 1ms
memory: 5876kb
input:
100 66 27 38 -18 -39 -35 -4 9 -18 -24 24 26 17 6 -4 -26 -46 -6 52 1 17 -15 73 26 31 -10 -46 -27 -4 23 17 -29 -74 -37 -11 -39 -4 2 -11 10 3 -34 3 -41 -39 0 10 -14 31 -3 -18 -10 -25 -30 10 0 -53 -33 -18 -31 38 31 10 -35 24 5 52 22 -60 -32 -11 -32 17 13 -81 -36 3 29 -18 -45 -67 -31 45 23 31 -17 45 30 -...
output:
49
result:
ok single line: '49'
Test #62:
score: 0
Wrong Answer
time: 1ms
memory: 5684kb
input:
100 -36 37 19 49 31 -23 -16 61 -22 -65 40 -23 -48 1 -2 -41 -1 25 15 55 16 -41 -28 -29 30 19 48 19 8 -29 0 37 -8 -59 31 31 11 -47 12 19 15 1 36 -17 -49 -11 -6 73 -5 -23 -31 -11 -46 25 -33 -35 -44 -5 -42 -35 -21 -53 30 -35 1 49 46 -5 35 -29 10 49 -3 55 28 -5 25 -41 12 73 40 31 -54 -17 56 7 27 -17 -17 ...
output:
1
result:
wrong answer 1st lines differ - expected: '54', found: '1'
Subtask #5:
score: 0
Skipped
Dependency #2:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%