QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#60410 | #2174. Which Planet is This?! | fstqwq# | WA | 210ms | 15200kb | C++17 | 3.5kb | 2022-11-04 15:34:46 | 2022-11-04 15:34:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 1000005, base = 1;
int fail[maxn];
void kmp(const vector<int> &s) {
int n = (int)s.size() - 1;
fail[0] = fail[1] = 0;
for (int i = 1; i < n; i++) {
int j = fail[i];
while (j && s[i + 1] != s[j + 1])
j = fail[j];
if (s[i + 1] == s[j + 1])
fail[i + 1] = j + 1;
else
fail[i + 1] = 0;
}
}
vector<int> match(const vector<int> &s, const vector<int> &t) {
int j = 0; // s in t, both 1-based
vector<int> ans;
for (int i = 1; i < (int)t.size(); i++) {
while (j && s[j + 1] != t[i])
j = fail[j];
if (s[j + 1] == t[i])
j++;
if (j == (int)s.size() - 1)
ans.push_back(i);
}
return ans;
}
vector<int> solve(int l, int r, const vector<vector<int>> &vec) {
if (l == r)
return vec[l];
int mid = (l + r) / 2;
auto u = solve(l, mid, vec), v = solve(mid + 1, r, vec);
sort(u.begin(), u.end());
sort(v.begin(), v.end());
vector<int> c;
int pt = 0;
for (int x : u) {
while (pt < (int)v.size() && v[pt] < x)
pt++;
if (pt < (int)v.size() && v[pt] == x)
c.push_back(x);
}
return c;
}
int main() {
int n;
scanf("%d", &n);
// vector<int> ax, ay, bx, by;
// ax.resize(n + 1);
// ay.resize(n + 1);
// bx.resize(n * 2 + 1);
// by.resize(n * 2 + 1);
map<int, vector<int> > mpa, mpb, oa, ob;
for (int i = 1; i <= n * 2; i++) {
int xa, xb, ya, yb;
scanf("%d.%d %d.%d", &xa, &xb, &ya, &yb);
int u = xa * base + xb, v = ya * base + yb;
v += 180 * base;
// y += 180;
// int u = (int)(x * base + 0.5), v = (int)(y * base + 0.5);
(i <= n ? mpa[u] : mpb[u]).push_back(v);
}
// oa = mpa;
// ob = mpb;
bool bad = false;
for (auto &[u, vec] : mpa) {
if (!mpb.count(u) || mpb[u].size() != vec.size()) {
bad = true;
break;
}
sort(vec.begin(), vec.end());
sort(mpb[u].begin(), mpb[u].end());
oa[u] = vec;
ob[u] = mpb[u];
auto work = [] (vector<int> &vec) {
// printf("(");
// for (int x : vec)
// printf(" %d", x);
// printf(" ) -> (");
vec.insert(vec.begin(), vec.back());
for (int i = (int)vec.size() - 1; i > 0; i--)
vec[i] -= vec[i - 1];
for (int &x : vec)
if (x < 0)
x += 360 * base;
vec[0] = 0;
// for (int x : vec)
// printf(" %d", x);
// printf(")\n");
};
mpb[u].insert(mpb[u].end(), mpb[u].begin(), mpb[u].end());
work(vec);
work(mpb[u]);
}
if (bad) {
printf("Different\n");
return 0;
}
vector<vector<int>> res;
for (auto &[u, vec] : mpa) {
// printf("u = %d\n", u);
// printf("vec:");
// for (int x : vec)
// printf(" %d", x);
// printf("\n");
// printf("mpb:");
// for (int x : mpb[u])
// printf(" %d", x);
// printf("\n");
kmp(vec);
auto tv = match(vec, mpb[u]);
// printf("tv:");
// for (int x : tv)
// printf(" %d", x);
// printf("\n");
res.push_back(vector<int>());
int len = (int)oa[u].size();
for (int i : tv)
if (i - len < len) {
int tmp = ob[u][i - len] - oa[u][0];
if (tmp < 360 * base)
tmp += 360 * base;
res.back().push_back(tmp);
}
// printf("? ");
// for (int x : res.back())
// printf("%d ", x);
// printf("\n\n");
memset(fail, 0, sizeof(int) * ((int)vec.size() + 3));
}
vector<int> ans = solve(0, (int)res.size() - 1, res);
if (!ans.empty())
printf("Same\n");
else
printf("Different\n");
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3564kb
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: 210ms
memory: 15200kb
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'