QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#227593#2174. Which Planet is This?!TWTP_TCTF#TL 0ms3828kbC++172.8kb2023-10-27 19:18:562023-10-27 19:18:56

Judging History

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

  • [2023-10-27 19:18:56]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3828kb
  • [2023-10-27 19:18: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 freq[mod + 5];

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 <= 2 * m; 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;
    vector<pair<int, int> > v1, v2;

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

    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    int cnt = 0;
    for (int i = 0; i < n;) {
        int j = i;
        cnt++;

        vector<int> a, b;
        while (j < n && v1[j].first == v1[i].first) {
            a.push_back(v1[j++].second);
        }

        j = i;
        while (j < n && v2[j].first == v2[i].first) {
            b.push_back(v2[j++].second);
        }

        if (v1[i].first != v2[i].first || (int) a.size() != (int) b.size()) {
            cout << "Different";
            return;
        }

        i = j;

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

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

        solve(da, db);
    }


    for (int i = 0; i < mod; i++) {
        if (freq[i] == cnt) {
            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: 3828kb

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: