QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#186371 | #2174. Which Planet is This?! | So_Stuffy# | WA | 642ms | 59404kb | C++20 | 6.2kb | 2023-09-23 18:33:51 | 2023-09-23 18:33:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
map < long long, long long > mp_N;
map < long long, set < long long > > mp1_N, mp2_N;
long long n, a_N, b_N, prv_N, i, px_N;
vector <int> zet(vector <int> &a) {
vector <int> z((int)a.size());
for (int i = 1, l = 0, r = 0; i < (int)a.size(); i++) {
if (i < r) {
z[i] = min(r - i, z[i - l]);
}
while (i + z[i] < (int)a.size() && a[z[i]] == a[i + z[i]]) {
z[i]++;
}
if (i + z[i] > r) {
l = i; r = i + z[i];
}
}
return z;
}
long long md(long long a){
return a < 0 ? a + 360 * 1e4 : a;
}
int cnt[360 * 10000 + 5];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector <int> div;
for (int i = 2; i < 360*10000; i++) {
if ((360 * 10000) % i == 0) {
div.push_back(i);
}
}
vector <int> vx1;
map <int, vector <int> > mp1, mp2;
for (int i = 0; i < n; i++) {
long double x, y;
cin >> x >> y; x += 90; y += 180;
x *= 10000; y *= 10000;
vx1.push_back(x);
mp1[x].push_back(y);
a_N = x;
b_N = y;
mp1_N[a_N].insert(b_N);
}
sort(vx1.begin(), vx1.end());
vector <int> vx2;
for (int i = 0; i < n; i++) {
long double x, y;
cin >> x >> y;
x += 90; y += 180;
x *= 10000; y *= 10000;
vx2.push_back(x);
mp2[x].push_back(y);
a_N = x;
b_N = y;
mp2_N[a_N].insert(b_N);
}
px_N = -1e10;
for (auto r : mp1_N){
if (mp2_N[r.first].size() != r.second.size()){
cout << "Different\n";
return 0;
}
prv_N = -1e10;
for (auto x : r.second){
if (prv_N != -1e10){
mp_N[md(x - prv_N)]++;
}
prv_N = x;
}
prv_N = -1e10;
for (auto x : mp2_N[r.first]){
if (prv_N != -1e10){
mp_N[md(x - prv_N)]--;
if (mp_N[md(x - prv_N)] < 0){
cout << "Different\n";
return 0;
}
prv_N = x;
}
}
if (px_N != -1e10){
for (auto x : mp1_N[r.first]){
auto it = mp1_N[px_N].lower_bound(x);
if (it == mp1_N[px_N].end()) it = mp1_N[px_N].begin();
mp_N[md(x - *it)]++;
}
for (auto x : mp2_N[r.first]){
auto it = mp2_N[px_N].lower_bound(x);
if (it == mp2_N[px_N].end()) it = mp2_N[px_N].begin();
mp_N[md(x - *it)]--;
if (mp_N[md(x - *it)] < 0){
cout << "Different\n";
return 0;
}
}
for (auto x : mp1_N[px_N]){
auto it = mp1_N[r.first].lower_bound(x);
if (it == mp1_N[r.first].end()) it = mp1_N[r.first].begin();
mp_N[md(x - *it)]++;
}
for (auto x : mp2_N[px_N]){
auto it = mp2_N[r.first].lower_bound(x);
if (it == mp2_N[r.first].end()) it = mp2_N[r.first].begin();
mp_N[md(x - *it)]--;
if (mp_N[md(x - *it)] < 0){
cout << "Different\n";
return 0;
}
}
}
px_N = r.first;
}
sort(vx2.begin(), vx2.end());
int i = 0;
while (i < n && vx1[i] == vx2[i]) {
i++;
}
if (i < n) {
cout << "Different";
return 0;
}
auto it1 = mp1.begin();
auto it2 = mp2.begin();
vector <pair <int, int> > v;
while (it1 != mp1.end()) {
auto v1 = it1 -> second;
auto v2 = it2 -> second;
if ((int)v1.size() != (int)v2.size()) {
cout << "Different";
return 0;
}
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
vector <int> d1, d2;
for (int i = 0; i < (int)v1.size(); i++) {
d1.push_back(v1[(i + 1) % (int)v1.size()] - v1[i]);
if (d1.back() < 0) {
d1.back() += 360 * 10000;
}
d2.push_back(v2[(i + 1) % (int)v1.size()] - v2[i]);
if (d2.back() < 0) {
d2.back() += 360 * 10000;
}
}
auto D1 = d1;
auto D2 = d2;
sort(d1.begin(), d1.end());
sort(d2.begin(), d2.end());
int i = 0;
while (i < (int)d1.size() && d1[i] == d2[i]) {
i++;
}
if (i < (int)d1.size()) {
cout << "Different";
return 0;
}
d1 = D1; d2 = D2;
d1.push_back(7*1e6);
for (auto x : d2) {
d1.push_back(x);
}
for (auto x : d2) {
d1.push_back(x);
}
auto z = zet(d1);
vector <int> sh;
for (int i = (int)d2.size() + 1; i < (int)d2.size() + (int)d2.size() + 1; i++) {
if (z[i] == (int)d2.size()) {
int j = i - (int)d2.size() - 1;
sh.push_back((v2[j] - v1[0] + 360 * 10000) % (360 * 10000));
}
}
if ((int)sh.size() == 0) {
cout << "Different";
return 0;
}
sort(sh.begin(), sh.end());
if ((int)sh.size() == 1) {
v.push_back({sh[0], 0});
} else {
v.push_back({sh[0], sh[1] - sh[0]});
}
it1++; it2++;
}
for (auto p : div) {
int sum = 0;
for (auto [x, d] : v) {
if (d % p == 0) {
cnt[x % p]++;
sum++;
}
}
bool gd = 1;
for (auto [x, d] : v) {
if (d % p == 0) {
gd &= (cnt[x % p] == sum);
}
}
if (!gd) {
cout << "Different";
return 0;
}
for (auto [x, d] : v) {
if (d % p == 0) {
cnt[x % p]--;
}
}
}
cout << "Same";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 3652kb
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: 642ms
memory: 59404kb
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'