QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#211959 | #2174. Which Planet is This?! | So_Stuffy | WA | 547ms | 37460kb | C++20 | 2.2kb | 2023-10-13 01:39:00 | 2023-10-13 01:39:00 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
ll n, i, p1[800501], p2[800501];
ld a, b;
pair < ll, ll > c1[400501], c2[400501], s[800501];
ll md(ll a){
return a < 0 ? a + 360 * 1e4 : a;
}
int main(){
cin >> n;
for (i = 1; i <= n; i++){
cin >> a >> b;
c1[i] = {a * 1e4, b * 1e4 + 360 * 1e4};
if (c1[i].second >= 360 * 1e4) c1[i].second -= 360 * 1e4;
}
for (i = 1; i <= n; i++){
cin >> a >> b;
c2[i] = {a * 1e4, b * 1e4 + 360 * 1e4};
if (c2[i].second >= 360 * 1e4) c2[i].second -= 360 * 1e4;
}
sort(c1 + 1, c1 + n + 1, [&](pair < ll, ll > i, pair < ll, ll > j){return i.second < j.second || (j.second == i.second && i.first < j.first);});
sort(c2 + 1, c2 + n + 1, [&](pair < ll, ll > i, pair < ll, ll > j){return i.second < j.second || (j.second == i.second && i.first < j.first);});
ll f1 = md(c1[1].second - c1[n].second), f2 = md(c2[1].second - c2[n].second);
for (i = n; i >= 2; i--){
c1[i].second -= c1[i - 1].second;
c2[i].second -= c2[i - 1].second;
}
c1[1].second = f1;
c2[1].second = f2;
for (i = 0; i < n; i++){
s[i] = c1[i + 1];
}
s[n] = {-1e9, -1e9};
for (i = n + 1; i <= n + 1 + n - 1; i++){
s[i] = c2[i - n];
}
for (i = 1; i <= n + 1 + n - 1; i++){
int j = p1[i - 1];
while (j > 0 && s[i] != s[j]){
j = p1[j - 1];
}
if (s[i] == s[j]) j++;
p1[i] = j;
}
reverse(c1 + 1, c1 + n + 1);
reverse(c2 + 1, c2 + n + 1);
for (i = 0; i < n; i++){
s[i] = c1[i + 1];
}
s[n] = {-1e9, -1e9};
for (i = n + 1; i <= n + 1 + n - 1; i++){
s[i] = c2[i - n];
}
for (i = 1; i <= n + 1 + n - 1; i++){
int j = p2[i - 1];
while (j > 0 && s[i] != s[j]){
j = p2[j - 1];
}
if (s[i] == s[j]) j++;
p2[i] = j;
}
// cout << p1[n + 1 + n - 1] << " " << p2[n + 1 + n - 1] << '\n';
if (p1[n + 1 + n - 1] + p2[n + 1 + n - 1] >= n) cout << "Same\n";
else cout << "Different\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5624kb
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: 547ms
memory: 37460kb
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'