QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#701143#2174. Which Planet is This?!gambit#WA 1080ms189080kbC++172.2kb2024-11-02 13:49:242024-11-02 13:49:24

Judging History

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

  • [2024-11-02 13:49:24]
  • 评测
  • 测评结果:WA
  • 用时:1080ms
  • 内存:189080kb
  • [2024-11-02 13:49:24]
  • 提交

answer

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
vi kmp_pi(vi &p) {
    int n = p.size(); vi pi(n);
    for (int i = 1, j = 0; i < n; i++) {
        while (j && p[i] != p[j]) j = pi[j - 1];
        if (p[i] == p[j]) pi[i] = ++j;
    }
    return pi;
}
vi kmp(vi &s, vi &p) {
    int n = s.size(), m = p.size();
    vi pi = kmp_pi(p), ret;
    for (int i = 0, j = 0; i < n; i++) {
        while (j && s[i] != p[j]) j = pi[j - 1];
        if (s[i] == p[j]) {
            if (j + 1 == m) ret.push_back(i - m + 1), j = pi[j];
            j++;
        }
    }
    return ret;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n; map<int, vi> p, q;
    for (int i = 0; i < n; i++) {
        double lat, lon; cin >> lat >> lon;
        int y = lat * 10000, x = lon * 10000;
        p[y].push_back(x);
    }
    for (int i = 0; i < n; i++) {
        double lat, lon; cin >> lat >> lon;
        int y = lat * 10000, x = lon * 10000;
        q[y].push_back(x);
    }
    bool good = true;
    set<int> st;
    for (int i = 0; i < 3600000; i++) st.insert(i);
    for (auto &[k, v]: p) sort(all(v));
    for (auto &[k, v]: q) sort(all(v));
    for (auto &[k, v]: p) {
        if (q.find(k) == q.end()) {good = false; break;}
        if (q[k].size() != v.size()) {good = false; break;}
        vi s(v.size()), t(q[k].size());
        for (int i = 0; i < (int)v.size(); i++) {
            s[i] = (v[(i + 1) % (int)v.size()] - v[i] + 3600000) % 3600000;
        }
        for (int i = 0; i < (int)q[k].size(); i++) {
            t[i] = (q[k][(i + 1) % (int)q[k].size()] - q[k][i] + 3600000) % 3600000;
        }
        int sz = s.size();
        for (int i = 0; i < sz; i++) s.push_back(s[i]);
        vi loc = kmp(s, t);
        if (loc.size() == 0) {good = false; break;}
        set<int> curset;
        for (auto &x: loc) {
            int val = (v[x] - q[k][0] + 3600000) % 3600000;
            if (st.find(val) != st.end()) curset.insert(val);
        }
        st = curset;
    }
    if (st.empty()) good = false;
    cout << (good ? "Same\n" : "Different\n");
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 834ms
memory: 172620kb

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: 1080ms
memory: 189080kb

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'