QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#186371#2174. Which Planet is This?!So_Stuffy#WA 642ms59404kbC++206.2kb2023-09-23 18:33:512023-09-23 18:33:51

Judging History

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

  • [2023-09-23 18:33:51]
  • 评测
  • 测评结果:WA
  • 用时:642ms
  • 内存:59404kb
  • [2023-09-23 18:33:51]
  • 提交

answer

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

map < long long, long long > mp_N;
map < long long, set < long long > > mp1_N, mp2_N;

long long n, a_N, b_N, prv_N, i, px_N;

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

long long md(long long a){
    return a < 0 ? a + 360 * 1e4 : a;
}

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);
        a_N = x;
        b_N = y;
        mp1_N[a_N].insert(b_N);
    }

    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);
        a_N = x;
        b_N = y;
        mp2_N[a_N].insert(b_N);
    }

    px_N = -1e10;
    for (auto r : mp1_N){
        if (mp2_N[r.first].size() != r.second.size()){
            cout << "Different\n";
            return 0;
        }
        prv_N = -1e10;
        for (auto x : r.second){
            if (prv_N != -1e10){
                mp_N[md(x - prv_N)]++;
            }
            prv_N = x;
        }

        prv_N = -1e10;
        for (auto x : mp2_N[r.first]){
            if (prv_N != -1e10){
                mp_N[md(x - prv_N)]--;
                if (mp_N[md(x - prv_N)] < 0){
                    cout << "Different\n";
                    return 0;
                }
                prv_N = x;
            }
        }

        if (px_N != -1e10){
            for (auto x : mp1_N[r.first]){
                auto it = mp1_N[px_N].lower_bound(x);
                if (it == mp1_N[px_N].end()) it = mp1_N[px_N].begin();
                mp_N[md(x - *it)]++;
            }
            for (auto x : mp2_N[r.first]){
                auto it = mp2_N[px_N].lower_bound(x);
                if (it == mp2_N[px_N].end()) it = mp2_N[px_N].begin();
                mp_N[md(x - *it)]--;
                if (mp_N[md(x - *it)] < 0){
                    cout << "Different\n";
                    return 0;
                }
            }

            for (auto x : mp1_N[px_N]){
                auto it = mp1_N[r.first].lower_bound(x);
                if (it == mp1_N[r.first].end()) it = mp1_N[r.first].begin();
                mp_N[md(x - *it)]++;
            }
            for (auto x : mp2_N[px_N]){
                auto it = mp2_N[r.first].lower_bound(x);
                if (it == mp2_N[r.first].end()) it = mp2_N[r.first].begin();
                mp_N[md(x - *it)]--;
                if (mp_N[md(x - *it)] < 0){
                    cout << "Different\n";
                    return 0;
                }
            }
        }
        px_N = r.first;
    }

    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;
        }
        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());
        if ((int)sh.size() == 1) {
            v.push_back({sh[0], 0});
        } 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";
}

詳細信息

Test #1:

score: 100
Accepted
time: 7ms
memory: 3652kb

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: 642ms
memory: 59404kb

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'