QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#381384 | #2174. Which Planet is This?! | SolitaryDream# | WA | 327ms | 59840kb | C++17 | 2.1kb | 2024-04-07 17:11:49 | 2024-04-07 17:11:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = (1ull << 61) - 1;
const int BASE = 407;
const int L = 3600000;
inline int Mul(int x, int y) {
return (__int128)x * y % mod;
}
int cnt[L];
int pwb[L];
inline void Fail() {
cout << "Different" << endl;
exit(0);
}
inline void Check(vector<int> a, vector<int> b) {
if (a.size() != b.size()) Fail();
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int n = a.size();
vector<int> va(n), vb(n);
for (int i = 0; i < n; ++i) va[i] = (a[(i + 1) % n] - a[i] + mod) % mod;
for (int i = 0; i < n; ++i) vb[i] = (b[(i + 1) % n] - b[i] + mod) % mod;
vector<int> ha(n), hb(n);
ha[0] = va[0];
for (int i = 1; i < n; ++i) ha[i] = (Mul(ha[i - 1], BASE) + va[i]) % mod;
hb[0] = vb[0];
for (int i = 1; i < n; ++i) hb[i] = (Mul(hb[i - 1], BASE) + vb[i]) % mod;
for (int i = 0; i < n; ++i) {
int vala = ha[n - 1];
int valb = hb[n - 1];
if (i) valb = (valb - Mul(hb[i - 1], pwb[n - i]) + mod) % mod;
if (i) valb = (Mul(valb, pwb[i]) + hb[i - 1]) % mod;
vala = (vala + mod) % mod;
valb = (valb + mod) % mod;
if (vala == valb) {
++cnt[(b[i] - a[0] + L) % L];
// cout << (b[i] - a[0] + L) % L << endl;
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
pwb[0] = 1;
for (int i = 1; i < L; ++i) pwb[i] = Mul(pwb[i - 1], BASE);
int n;
cin >> n;
map<double, pair<vector<int>, vector<int>>> mp;
for (int i = 1; i <= n; ++i) {
double x, y;
cin >> x >> y;
int ty = ((int)round(y * 10000) + L) % L;
mp[x].first.push_back(ty);
}
for (int i = 1; i <= n; ++i) {
double x, y;
cin >> x >> y;
int ty = ((int)round(y * 10000) + L) % L;
mp[x].second.push_back(ty);
}
for (auto [x, pvv] : mp) Check(pvv.first, pvv.second);
cout << (*max_element(cnt, cnt + L) == mp.size() ? "Same" : "Different") << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 28ms
memory: 31880kb
input:
3 10 0 20 40 30 -15 40 -15 20 0 30 40
output:
Different
result:
ok single line: 'Different'
Test #2:
score: 0
Accepted
time: 327ms
memory: 59840kb
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:
Same
result:
ok single line: 'Same'
Test #3:
score: -100
Wrong Answer
time: 272ms
memory: 55236kb
input:
299998 -0.0045 -42.0335 -0.0045 -106.8631 -0.0045 176.8211 -0.0045 100.6703 -0.0045 168.0453 -0.0045 -100.7977 -0.0045 -31.7881 -0.0045 -43.3799 -0.0045 -87.3392 -0.0045 30.4474 -0.0045 -7.4550 -0.0045 106.5476 -0.0045 -3.9185 -0.0045 -56.8153 -0.0045 -146.7755 -0.0045 -76.6043 -0.0045 57.1774 -0.00...
output:
Different
result:
wrong answer 1st lines differ - expected: 'Same', found: 'Different'