QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#211948#2174. Which Planet is This?!So_StuffyWA 528ms40068kbC++202.0kb2023-10-13 01:10:062023-10-13 01:10:06

Judging History

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

  • [2023-10-13 01:10:06]
  • 评测
  • 测评结果:WA
  • 用时:528ms
  • 内存:40068kb
  • [2023-10-13 01:10:06]
  • 提交

answer

#include <bits/stdc++.h>

#define ll long long
#define ld long double

using namespace std;

ll n, i, p1[800501], p2[800501];

ld a, b;

pair < ll, ll > c1[400501], c2[400501], s[800501];

int main(){
    cin >> n;

    for (i = 1; i <= n; i++){
        cin >> a >> b;
        c1[i] = {a * 1e4, b * 1e4 + 180 * 1e4};
    }

    for (i = 1; i <= n; i++){
        cin >> a >> b;
        c2[i] = {a * 1e4, b * 1e4 + 180 * 1e4};
    }

    sort(c1 + 1, c1 + n + 1, [&](pair < ll, ll > i, pair < ll, ll > j){return i.second < j.second || (j.second == i.second && i.first < j.first);});
    sort(c2 + 1, c2 + n + 1, [&](pair < ll, ll > i, pair < ll, ll > j){return i.second < j.second || (j.second == i.second && i.first < j.first);});
    ll f1 = -c1[n].second + c1[1].second, f2 = -c2[n].second + c2[1].second;
    for (i = n; i >= 2; i--){
        c1[i].second -= c1[i - 1].second;
        c2[i].second -= c2[i - 1].second;
    }
    c1[1].second = f1;
    c2[1].second = f2;

    for (i = 0; i < n; i++){
        s[i] = c1[i + 1];
    }
    s[n] = {-1e9, -1e9};
    for (i = n + 1; i <= n + 1 + n - 1; i++){
        s[i] = c2[i - n];
    }

    for (i = 1; i <= n + 1 + n - 1; i++){
        int j = p1[i - 1];
        while (j > 0 && s[i] != s[j]){
            j = p1[j - 1];
        }
        if (s[i] == s[j]) j++;
        p1[i] = j;
    }

    reverse(c1 + 1, c1 + n + 1);
    reverse(c2 + 1, c2 + n + 1);
    for (i = 0; i < n; i++){
        s[i] = c1[i + 1];
    }
    s[n] = {-1e9, -1e9};
    for (i = n + 1; i <= n + 1 + n - 1; i++){
        s[i] = c2[i - n];
    }

    for (i = 1; i <= n + 1 + n - 1; i++){
        int j = p2[i - 1];
        while (j > 0 && s[i] != s[j]){
            j = p2[j - 1];
        }
        if (s[i] == s[j]) j++;
        p2[i] = j;
    }

//    cout << p1[n + 1 + n - 1] << " " << p2[n + 1 + n - 1] << '\n';
    if (p1[n + 1 + n - 1] + p2[n + 1 + n - 1] >= n) cout << "Same\n";
    else cout << "Different\n";
}

详细

Test #1:

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

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: 528ms
memory: 40068kb

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'