QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#381317#2174. Which Planet is This?!SolitaryDream#WA 315ms63456kbC++172.0kb2024-04-07 16:52:252024-04-07 16:55:15

Judging History

你现在查看的是最新测评结果

  • [2024-04-07 16:55:15]
  • 评测
  • 测评结果:WA
  • 用时:315ms
  • 内存:63456kb
  • [2024-04-07 16:52:25]
  • 提交

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]);
    for (int i = 0; i < n; ++i) vb[i] = (b[(i + 1) % n] - b[i]);
    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;
        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: 26ms
memory: 32600kb

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: 315ms
memory: 63456kb

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: 267ms
memory: 58628kb

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'