QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#376638 | #2174. Which Planet is This?! | installb# | WA | 304ms | 30728kb | C++20 | 2.4kb | 2024-04-04 14:20:06 | 2024-04-04 14:20:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 3600000;
const int B = 4000001;
const int P0 = 1000000007;
const int P1 = 998244353;
int n;
vector <int> va[N],vb[N];
int pB[2][N],sa[N],sb[N],hb[2][N];
bool solve(){
cin >> n;
for(int i = 1;i <= n;i ++){
db x,y; cin >> x >> y;
int cx = x * 10000 + 900000;
int cy = y * 10000 + 1800000;
va[cx].push_back(cy);
}
for(int i = 1;i <= n;i ++){
db x,y; cin >> x >> y;
int cx = x * 10000 + 900000;
int cy = y * 10000 + 1800000;
vb[cx].push_back(cy);
}
pB[0][0] = pB[1][0] = 1;
for(int i = 1;i <= n + n;i ++){
pB[0][i] = 1ll * B * pB[0][i - 1] % P0;
pB[1][i] = 1ll * B * pB[1][i - 1] % P1;
}
int num = 0;
map <int,int> mp;
for(int i = 0;i <= 1800000;i ++){
if(va[i].size() != vb[i].size()) return 0;
if(va[i].size() == 0) continue;
num ++;
sort(va[i].begin(),va[i].end());
sort(vb[i].begin(),vb[i].end());
int sz = va[i].size();
for(int j = 1;j < sz;j ++) sa[i] = (va[i][j] - va[i][j - 1] + N) % N;
sa[sz] = (va[i][0] - va[i].back() + N) % N;
for(int j = 1;j < sz;j ++) sb[i] = (vb[i][j] - vb[i][j - 1] + N) % N;
sb[sz] = (vb[i][0] - vb[i].back() + N) % N;
for(int j = sz + 1;j <= sz + sz;j ++) sb[j] = sb[j - sz];
for(int j = 1;j <= sz + sz;j ++){
hb[0][j] = (hb[0][j - 1] + 1ll * pB[0][j - 1] * sb[j]) % P0;
hb[1][j] = (hb[1][j - 1] + 1ll * pB[1][j - 1] * sb[j]) % P1;
}
int xa[2] = {0};
for(int j = 1;j <= sz;j ++){
xa[0] = (xa[0] + 1ll * pB[0][j - 1] * sa[j]) % P0;
xa[1] = (xa[1] + 1ll * pB[1][j - 1] * sa[j]) % P1;
}
for(int j = 1;j <= sz;j ++){
int xb[2] = {0};
xb[0] = (hb[0][j + sz - 1] - hb[0][j - 1] + P0) % P0;
xb[1] = (hb[1][j + sz - 1] - hb[1][j - 1] + P1) % P1;
if(1ll * xa[0] * pB[0][j - 1] % P0 == xb[0] && 1ll * xa[1] * pB[1][j - 1] % P1 == xb[1])
mp[(vb[i][j - 1] - va[i][0] + N) % N] ++;
}
}
for(auto it = mp.begin();it != mp.end();it ++){
if(it->second == num) return 1;
}
return 0;
}
int main(){
ios::sync_with_stdio(false);
cout << (solve() ? "Same" : "Different") << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 7820kb
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: 304ms
memory: 30288kb
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: 256ms
memory: 30728kb
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'