QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#179766 | #2174. Which Planet is This?! | Alleks_B | WA | 549ms | 18924kb | C++14 | 2.6kb | 2023-09-15 03:20:26 | 2023-09-15 03:20:27 |
Judging History
answer
#include <bits/stdc++.h>
#define L 800005
#define SHIFT_DECIMALS 10000
#define DEG 360 * SHIFT_DECIMALS
using namespace std;
int n;
pair <int, int> a[L], b[L];
int f[L];
bool cmp(const pair <int, int> &A, const pair <int, int> &B) {
if (A.second == B.second)
return A.first < B.first;
return A.second < B.second;
}
int LMSR_a() {
int p = 0;
for (int i = n; i < 2 * n; i++)
a[i] = a[i - n];
for (int i = 0; i < 2 * n; i++)
f[i] = -1;
int l = 1;
for (int r = 1; r < 2 * n; r++) {
l = f[r - p - 1];
while (l != -1 && a[p + l + 1] != a[r]) {
if ((a[l + p + 1].second == a[r].second && a[l + p + 1].first > a[r].first) || a[l + p + 1].second > a[r].second)
p = r - l - 1;
l = f[l];
}
if (l == -1 && a[p + l + 1] != a[r]) {
if ((a[l + p + 1].second == a[r].second && a[l + p + 1].first > a[r].first) || a[l + p + 1].second > a[r].second)
p = r;
f[r - p] = -1;
}
else
f[r - p] = l + 1;
}
return p;
}
int LMSR_b() {
int p = 0;
for (int i = n; i < 2 * n; i++)
b[i] = b[i - n];
for (int i = 0; i < 2 * n; i++)
f[i] = -1;
int l = 1;
for (int r = 1; r < 2 * n; r++) {
l = f[r - p - 1];
while (l != -1 && b[p + l + 1] != b[r]) {
if ((b[l + p + 1].second == b[r].second && b[l + p + 1].first > b[r].first) || b[l + p + 1].second > b[r].second)
p = r - l - 1;
l = f[l];
}
if (l == -1 && b[p + l + 1] != b[r]) {
if ((b[l + p + 1].second == b[r].second && b[l + p + 1].first > b[r].first) || b[l + p + 1].second > b[r].second)
p = r;
f[r - p] = -1;
}
else
f[r - p] = l + 1;
}
return p;
}
int main(){
cin >> n;
for (int i = 0; i < n; i++) {
double x, y;
cin >> x >> y;
x *= SHIFT_DECIMALS;
y *= SHIFT_DECIMALS;
a[i] = {x, y};
}
for (int i = 0; i < n; i++) {
double x, y;
cin >> x >> y;
x *= SHIFT_DECIMALS;
y *= SHIFT_DECIMALS;
b[i] = {x, y};
}
sort(a, a + n, cmp);
sort(b, b + n, cmp);
int aux_a = a[0].second, aux_b = b[0].second;
for (int i = 0; i < n - 1; i++) {
a[i].second = a[i + 1].second - a[i].second;
b[i].second = b[i + 1].second - b[i].second;
}
a[n - 1].second = DEG + aux_a - a[n - 1].second;
b[n - 1].second = DEG + aux_b - b[n - 1].second;
bool ok = true;
int shift_a = LMSR_a(), shift_b = LMSR_b();
for (int i = 0; i < n; i++)
if (a[(i + shift_a) % n] != b[(i + shift_b) % n])
ok = false;
if (ok)
cout << "Same\n";
else
cout << "Different\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7812kb
input:
3 10 0 20 40 30 -15 40 -15 20 0 30 40
output:
Different
result:
ok single line: 'Different'
Test #2:
score: -100
Wrong Answer
time: 549ms
memory: 18924kb
input:
359998 -0.0045 96.8638 -0.0045 -79.2284 -0.0045 -50.4113 -0.0045 -79.0394 -0.0045 -24.9710 -0.0045 -142.9880 -0.0045 50.6344 -0.0045 125.9464 -0.0045 -17.3039 -0.0045 42.3454 -0.0045 130.6138 -0.0045 -106.4363 -0.0045 -95.9378 -0.0045 90.7312 -0.0045 75.7615 -0.0045 -66.9785 -0.0045 -81.0752 -0.0045...
output:
Different
result:
wrong answer 1st lines differ - expected: 'Same', found: 'Different'