QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#179766#2174. Which Planet is This?!Alleks_BWA 549ms18924kbC++142.6kb2023-09-15 03:20:262023-09-15 03:20:27

Judging History

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

  • [2023-09-15 03:20:27]
  • 评测
  • 测评结果:WA
  • 用时:549ms
  • 内存:18924kb
  • [2023-09-15 03:20:26]
  • 提交

answer

#include <bits/stdc++.h>
#define L 800005
#define SHIFT_DECIMALS 10000
#define DEG 360 * SHIFT_DECIMALS
using namespace std;

int n;
pair <int, int> a[L], b[L];
int f[L];

bool cmp(const pair <int, int> &A, const pair <int, int> &B) {
  if (A.second == B.second)
    return A.first < B.first;
  return A.second < B.second;
}

int LMSR_a() {
  int p = 0;
  for (int i = n; i < 2 * n; i++)
    a[i] = a[i - n];
  for (int i = 0; i < 2 * n; i++)
    f[i] = -1;
  int l = 1;
  for (int r = 1; r < 2 * n; r++) {
    l = f[r - p - 1];
    while (l != -1 && a[p + l + 1] != a[r]) {
      if ((a[l + p + 1].second == a[r].second && a[l + p + 1].first > a[r].first) || a[l + p + 1].second > a[r].second)
        p = r - l - 1;
      l = f[l];
    }
    if (l == -1 && a[p + l + 1] != a[r]) {
      if ((a[l + p + 1].second == a[r].second && a[l + p + 1].first > a[r].first) || a[l + p + 1].second > a[r].second)
        p = r;
      f[r - p] = -1;
    }
    else
      f[r - p] = l + 1;
  }
  return p;
}

int LMSR_b() {
  int p = 0;
  for (int i = n; i < 2 * n; i++)
    b[i] = b[i - n];
  for (int i = 0; i < 2 * n; i++)
    f[i] = -1;
  int l = 1;
  for (int r = 1; r < 2 * n; r++) {
    l = f[r - p - 1];
    while (l != -1 && b[p + l + 1] != b[r]) {
      if ((b[l + p + 1].second == b[r].second && b[l + p + 1].first > b[r].first) || b[l + p + 1].second > b[r].second)
        p = r - l - 1;
      l = f[l];
    }
    if (l == -1 && b[p + l + 1] != b[r]) {
      if ((b[l + p + 1].second == b[r].second && b[l + p + 1].first > b[r].first) || b[l + p + 1].second > b[r].second)
        p = r;
      f[r - p] = -1;
    }
    else
      f[r - p] = l + 1;
  }
  return p;
}

int main(){
  cin >> n;
  for (int i = 0; i < n; i++) {
    double x, y;
    cin >> x >> y;
    x *= SHIFT_DECIMALS;
    y *= SHIFT_DECIMALS;
    a[i] = {x, y};
  }
  for (int i = 0; i < n; i++) {
    double x, y;
    cin >> x >> y;
    x *= SHIFT_DECIMALS;
    y *= SHIFT_DECIMALS;
    b[i] = {x, y};
  }
  sort(a, a + n, cmp);
  sort(b, b + n, cmp);
  int aux_a = a[0].second, aux_b = b[0].second;
  for (int i = 0; i < n - 1; i++) {
    a[i].second = a[i + 1].second - a[i].second;
    b[i].second = b[i + 1].second - b[i].second;
  }
  a[n - 1].second = DEG + aux_a - a[n - 1].second;
  b[n - 1].second = DEG + aux_b - b[n - 1].second;
  bool ok = true;
  int shift_a = LMSR_a(), shift_b = LMSR_b();
  for (int i = 0; i < n; i++)
    if (a[(i + shift_a) % n] != b[(i + shift_b) % n])
      ok = false;
  if (ok)
    cout << "Same\n";
  else
    cout << "Different\n";
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7812kb

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: 549ms
memory: 18924kb

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'