QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#94664 | #2174. Which Planet is This?! | 8BQube# | WA | 392ms | 17096kb | C++20 | 2.8kb | 2023-04-07 14:27:38 | 2023-04-07 14:27:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define pb push_back
#define ALL(v) v.begin(), v.end()
const int C = 10000;
const int AC = 360 * C;
pii arr[400005], brr[400005];
vector<int> mcp(vector<int> v, int &off) {
int n = SZ(v), i = 0, j = 1;
for (int k = 0; k < n; ++k)
v.pb(v[k]);
while (i < n && j < n) {
int k = 0;
while (k < n && v[i + k] == v[j + k]) ++k;
if (v[i + k] <= v[j + k]) j += k + 1;
else i += k + 1;
if (i == j) ++j;
}
int ans = i < n ? i : j;
off = ans;
return vector<int>(v.begin() + ans, v.begin() + ans + n);
}
int F[400005];
void fail(vector<int> &B) {
F[0] = -1, F[1] = 0;
for (int i = 1, j = 0; i < SZ(B); F[++i] = ++j) {
while (j != -1 && B[i] != B[j]) j = F[j];
}
}
int vis[AC];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, tag = 0;
cin >> n;
for (int i = 1; i <= n; ++i) {
double a, b;
cin >> a >> b;
arr[i] = pii(a * C, b * C);
}
for (int i = 1; i <= n; ++i) {
double a, b;
cin >> a >> b;
brr[i] = pii(a * C, b * C);
}
auto diff = [&]() {
cout << "Different\n";
exit(0);
};
auto cyc = [&](int x) {
return (x % AC + AC) % AC;
};
sort(arr + 1, arr + n + 1);
sort(brr + 1, brr + n + 1);
for (int i = 1, j = 1; i <= n; i = j) {
++tag;
while (j <= n && arr[i].X == arr[j].X) {
if (arr[j].X != brr[j].X) diff();
++j;
}
vector<int> da, db;
da.pb(cyc(arr[i].Y - arr[j - 1].Y));
db.pb(cyc(brr[i].Y - brr[j - 1].Y));
for (int k = i + 1; k < j; ++k) {
da.pb(cyc(arr[k].Y - arr[k - 1].Y));
db.pb(cyc(brr[k].Y - brr[k - 1].Y));
}
int ofa, ofb;
mcp(da, ofa).swap(da);
mcp(db, ofb).swap(db);
if (da != db) diff();
fail(da);
vector<int> yes;
if (F[SZ(da)] * 2 < SZ(da) || SZ(da) % (SZ(da) - F[SZ(da)]) != 0) yes.pb(cyc(brr[i + ofb].Y - arr[i + ofa].Y));
else {
for (int k = 0; k < SZ(da); k += SZ(da) - F[SZ(da)])
yes.pb(cyc(brr[i + ofb].Y - arr[i + (ofa + k) % SZ(da)].Y));
}
sort(ALL(yes)), yes.resize(unique(ALL(yes)) - yes.begin());
for (int k : yes)
++vis[k];
/*for (int k = 0; k < SZ(da); ++k)
cerr << da[k] << " ";
cerr << endl;
for (int k = 0; k < SZ(db); ++k)
cerr << db[k] << " ";
cerr << endl;
cerr << arr[i].X << ": ";
for (int k : yes)
cerr << k << " ";
cerr << endl;*/
}
if (*max_element(vis, vis + AC) != tag) diff();
cout << "Same\n";
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 7792kb
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: 392ms
memory: 17096kb
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'