QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#227582#2174. Which Planet is This?!TWTP_TCTF#TL 0ms3548kbC++172.6kb2023-10-27 19:05:562023-10-27 19:05:57

Judging History

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

  • [2023-10-27 19:05:57]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3548kb
  • [2023-10-27 19:05:56]
  • 提交

answer

#include<iostream>
#include <bits/stdc++.h>

#define ld long double
#define ll long long
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 2e5 + 5, mod = 360 * 10000;
int n;
int freq[mod + 1];

void solve(vector<pair<int, int> > &a, vector<pair<int, int> > &b) {
    b.push_back({-1, -1});
    int m = a.size();
    for (auto i: a) {
        b.push_back(i);
    }
    for (auto i: a) {
        b.push_back(i);
    }

    int n = b.size();
    vector<int> z(n);
    set<int> vis;
    for (int i = 1; i < n; i++) {
        while (i + z[i] < n && b[z[i]].second == b[i + z[i]].second) {
            z[i]++;
        }
        if (z[i] == m) {
            int d = b[i].first - b[0].first;
            d = (d % mod + mod) % mod;
            vis.insert(d);
        }
    }
    for (auto i: vis) {
        freq[i]++;
    }
}

int get_val(string s) {
    int n = s.size();
    int idx = s.find('.');
    if (idx == -1) {
        s += "0000";
    } else {
        int rem = 4 - (s.size() - idx - 1);
        s.erase(s.begin() + idx);
        while (rem--) {
            s += '0';
        }
    }
    return stoi(s);
}

void doWork() {
    int n;
    cin >> n;
    map<int, vector<int> > v1, v2;
    for (int i = 0; i < n; i++) {
        string s1, s2;
        cin >> s1 >> s2;
        v1[get_val(s1)].push_back(get_val(s2));
    }
    for (int i = 0; i < n; i++) {
        string s1, s2;
        cin >> s1 >> s2;
        v2[get_val(s1)].push_back(get_val(s2));
    }

    for (auto i: v1) {
        vector<int> &a = i.second;
        vector<int> &b = v2[i.first];

        if (a.size() != b.size()) {
            cout << "Different";
            return;
        }
        for (int i = 0; i < a.size(); i++) {
            a[i] = (a[i] % mod + mod) % mod;
            b[i] = (b[i] % mod + mod) % mod;
        }
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());

        int m = a.size();
        vector<pair<int, int>> da(m), db(m);
        for (int i = 0; i < m; i++) {
            da[i] = {a[i], a[(i + 1) % m] - a[i]};
            if (da[i].second < 0)da[i].second += mod;

            db[i] = {b[i], b[(i + 1) % m] - b[i]};
            if (db[i].second < 0)db[i].second += mod;
        }

        solve(da, db);
    }
    for (int i = 0; i < mod; i++) {
        if (freq[i] == v1.size()) {
            cout << "same";
            return;
        }
    }
    cout << "Different";
}

int main() {
    IO
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; i++) {
        //cout << "Case #" << i << ": ";
        doWork();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3548kb

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
Time Limit Exceeded

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:


result: