QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#186379#2174. Which Planet is This?!So_Stuffy#WA 308ms18552kbC++204.1kb2023-09-23 18:55:152023-09-23 18:55:16

Judging History

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

  • [2023-09-23 18:55:16]
  • 评测
  • 测评结果:WA
  • 用时:308ms
  • 内存:18552kb
  • [2023-09-23 18:55:15]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

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;
}

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);
    }

    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);
    }
    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;
        }

        i = 0;
        while (i + 1 < n && d1[i] == d1[i + 1]) {
            i++;
        }
        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());
        sh.resize(unique(sh.begin(), sh.end()) - sh.begin());
        if ((int)sh.size() == 1) {
            v.push_back({sh[0], 360*10000});
        } 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: 3596kb

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: 308ms
memory: 18552kb

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'