QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#376636 | #2174. Which Planet is This?! | willow# | WA | 177ms | 125180kb | C++17 | 3.5kb | 2024-04-04 14:17:22 | 2024-04-04 14:17:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int base1 = 19260817, base2 = 919260817, mod1 = 998244353, mod2 = 1e9 + 9;
int Add(int x, int y, int mod) {
return (x += y) >= mod ? x - mod : x;
}
int Sub(int x, int y, int mod) {
return (x -= y) < 0 ? x + mod : x;
}
int Mul(int x, int y, int mod) {
return 1ll * x * y % mod;
}
int Pow(int x, int y, int mod) {
int res = 1;
for(; y; x = Mul(x, x, mod), y >>= 1)
if(y & 1)
res = Mul(res, x, mod);
return res;
}
typedef pair<int, int> pii;
pii base = {base1, base2};
#define x first
#define y second
pii operator + (pii a, pii b) {
return {Add(a.x, b.x, mod1), Add(a.y, b.y, mod2)};
}
pii operator - (pii a, pii b) {
return {Sub(a.x, b.x, mod1), Sub(a.y, b.y, mod2)};
}
pii operator * (pii a, pii b) {
return {Mul(a.x, b.x, mod1), Mul(a.y, b.y, mod2)};
}
#undef x
#undef y
const int maxn = 8e5 + 5, maxl = 2e6 + 5;
pii pw[maxn], ipw[maxn], h1[maxn];
int n, dif1[maxn], dif2[maxn];
vector<int> pos1[maxl], pos2[maxl];
set<int> now;
int main() {
n = 8e5;
pw[0] = {1, 1};
for(int i = 1; i <= n; ++ i) {
pw[i] = pw[i - 1] * base;
}
ipw[n].first = Pow(pw[n].first, mod1 - 2, mod1);
ipw[n].second = Pow(pw[n].second, mod2 - 2, mod2);
for(int i = n; i; -- i) {
ipw[i - 1] = ipw[i] * base;
// assert(pw[i] * ipw[i] == make_pair(1, 1));
// cerr << (pw[i] * ipw[i]).first << " " << (pw[i] * ipw[i]).second << endl;
}
scanf("%d", &n);
for(int i = 1; i <= n; ++ i) {
double x, y;
scanf("%lf%lf", &x, &y);
int dx = (int)round((x + 90) * 10000);
int dy = (int)round((y + 180) * 10000);
pos1[dx].push_back(dy);
}
for(int i = 1; i <= n; ++ i) {
double x, y;
scanf("%lf%lf", &x, &y);
int dx = (int)round((x + 90) * 10000);
int dy = (int)round((y + 180) * 10000);
pos2[dx].push_back(dy);
}
int all = 3600000, fst = 1;
for(int x = 0; x < maxl; ++ x) {
if(pos1[x].size() != pos2[x].size()) {
puts("Different");
return 0;
}
if(pos1[x].size()) {
// cerr << "x = " << x << "?? " << endl;
set<int> nxt;
nxt.clear();
int w = pos1[x].size();
// for(int i = 0; i < w; ++ i) {
// cerr << pos1[x][i] << " " << pos2[x][i] << endl;
// }
pii h2 = {0, 0};
for(int i = 0; i < w; ++ i) {
dif1[i] = dif1[i + w] = (pos1[x][(i + 1) % w] - pos1[x][i] + all) % all;
dif2[i] = (pos2[x][(i + 1) % w] - pos2[x][i] + all) % all;
// cerr << dif1[i] << " " << dif2[i] << endl;
h2 = h2 + pw[i] * make_pair(dif2[i], dif2[i]);
}
for(int i = 0; i < 2 * w; ++ i) {
h1[i + 1] = h1[i] + pw[i] * make_pair(dif1[i], dif1[i]);
}
for(int i = 0; i < w; ++ i) {
if((h1[i + w] - h1[i]) * ipw[i] == h2) {
int dy = pos2[x][0] - pos1[x][i];
// cerr << "dx = " << x << " Fuck " << dy << " " << now.count(dy) << endl;
if(fst || now.count(dy)) {
// cerr << "? " << dy << endl;
nxt.insert(dy);
}
}
}
swap(now, nxt);
// for(auto x : now)
// cerr << x << " ";cerr << endl;
fst = 0;
}
}
puts(now.size() ? "Same" : "Different");
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 20ms
memory: 114276kb
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: 177ms
memory: 125180kb
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'