QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#380348#2174. Which Planet is This?!neal2022WA 269ms33840kbC++232.4kb2024-04-07 01:03:002024-04-07 01:03:01

Judging History

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

  • [2024-04-07 01:03:01]
  • 评测
  • 测评结果:WA
  • 用时:269ms
  • 内存:33840kb
  • [2024-04-07 01:03:00]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

vector<int> get_next(vector<i64>& pat) {
  int m = (int)pat.size();
  vector<int> nex(m);
  for (int i = 1, j = 0; i < m; i++) {
    while (j && pat[j] != pat[i]) j = nex[j - 1];
    if (pat[j] == pat[i]) j++;
    nex[i] = j;
  }
  return nex;
}

int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);
  int n;
  std::cin >> n;
  auto get_map = [&] {
    std::vector<std::array<double, 2>> a(n);
    std::map<i64, vector<i64>> mp;
    for (auto& [x, y] : a) std::cin >> x >> y, mp[i64(x * 10000)].push_back(i64(y * 10000));
    return mp;
  };
  auto mp1 = get_map();
  auto mp2 = get_map();

  std::set<i64> can;
  bool init = false;

  constexpr i64 MOD = 360 * 10000;

  auto update = [&](std::vector<i64> v) {
    for (auto& x : v) {
      x = (x % MOD + MOD) % MOD;
    }
    if (!init) {
      for (auto& x : v) can.insert(x);
      init = true;
      return;
    }
    std::set<i64> good;
    for (auto& x : v) {
      if (can.contains(x)) good.insert(x);
    }
    can = good;
  };

  for (auto& [k, v1] : mp1) {
    auto& v2 = mp2[k];
    if (v1.size() != v2.size()) {
      std::cout << "Different\n";
      return 0;
    }
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
    if (v1.size() == 1) {
      update({v1[0] - v2[0]});
      continue;
    }

    auto get_diff = [&](std::vector<i64> v) {
      std::vector<i64> diff;
      for (int i = 0; i < v.size(); i++) {
        i64 d = v[(i + 1) % v.size()] - v[i];
        d = (d % MOD + MOD) % MOD;
        diff.push_back(d);
      }
      return diff;
    };
    auto d1 = get_diff(v1);
    auto d2 = get_diff(v2);
    for (int i = 0; i < v1.size(); i++) d1.push_back(d1[i]);

    std::vector<i64> now;

    auto& pat = d2;
    auto& txt = d1;
    auto m = d2.size();
    auto nex = get_next(pat);
    for (int i = 0, j = 0; i < d2.size(); i++) {
      while (j && pat[j] != txt[i]) j = nex[j - 1];
      if (pat[j] == txt[i]) j++;
      if (j == m) {
        // do what you want with the match
        // start index is `i - m + 1`
        now.push_back(v1[i - m + 1] - v2[0]);
        j = nex[j - 1];
      }
    }
    update(now);
  }
  if (can.size() && init) {
    std::cout << "Same\n";
  } else {
    std::cout << "Different\n";
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 269ms
memory: 33840kb

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'