QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#701143 | #2174. Which Planet is This?! | gambit# | WA | 1080ms | 189080kb | C++17 | 2.2kb | 2024-11-02 13:49:24 | 2024-11-02 13:49:24 |
Judging History
answer
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
vi kmp_pi(vi &p) {
int n = p.size(); vi pi(n);
for (int i = 1, j = 0; i < n; i++) {
while (j && p[i] != p[j]) j = pi[j - 1];
if (p[i] == p[j]) pi[i] = ++j;
}
return pi;
}
vi kmp(vi &s, vi &p) {
int n = s.size(), m = p.size();
vi pi = kmp_pi(p), ret;
for (int i = 0, j = 0; i < n; i++) {
while (j && s[i] != p[j]) j = pi[j - 1];
if (s[i] == p[j]) {
if (j + 1 == m) ret.push_back(i - m + 1), j = pi[j];
j++;
}
}
return ret;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n; map<int, vi> p, q;
for (int i = 0; i < n; i++) {
double lat, lon; cin >> lat >> lon;
int y = lat * 10000, x = lon * 10000;
p[y].push_back(x);
}
for (int i = 0; i < n; i++) {
double lat, lon; cin >> lat >> lon;
int y = lat * 10000, x = lon * 10000;
q[y].push_back(x);
}
bool good = true;
set<int> st;
for (int i = 0; i < 3600000; i++) st.insert(i);
for (auto &[k, v]: p) sort(all(v));
for (auto &[k, v]: q) sort(all(v));
for (auto &[k, v]: p) {
if (q.find(k) == q.end()) {good = false; break;}
if (q[k].size() != v.size()) {good = false; break;}
vi s(v.size()), t(q[k].size());
for (int i = 0; i < (int)v.size(); i++) {
s[i] = (v[(i + 1) % (int)v.size()] - v[i] + 3600000) % 3600000;
}
for (int i = 0; i < (int)q[k].size(); i++) {
t[i] = (q[k][(i + 1) % (int)q[k].size()] - q[k][i] + 3600000) % 3600000;
}
int sz = s.size();
for (int i = 0; i < sz; i++) s.push_back(s[i]);
vi loc = kmp(s, t);
if (loc.size() == 0) {good = false; break;}
set<int> curset;
for (auto &x: loc) {
int val = (v[x] - q[k][0] + 3600000) % 3600000;
if (st.find(val) != st.end()) curset.insert(val);
}
st = curset;
}
if (st.empty()) good = false;
cout << (good ? "Same\n" : "Different\n");
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 834ms
memory: 172620kb
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: 1080ms
memory: 189080kb
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'