QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#94653 | #2174. Which Planet is This?! | 8BQube# | WA | 519ms | 18032kb | C++20 | 2.8kb | 2023-04-07 14:14:54 | 2023-04-07 14:16:37 |
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);
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: 7620kb
input:
3 10 0 20 40 30 -15 40 -15 20 0 30 40
output:
Different
result:
ok single line: 'Different'
Test #2:
score: 0
Accepted
time: 383ms
memory: 18032kb
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:
Same
result:
ok single line: 'Same'
Test #3:
score: 0
Accepted
time: 325ms
memory: 13980kb
input:
299998 -0.0045 -42.0335 -0.0045 -106.8631 -0.0045 176.8211 -0.0045 100.6703 -0.0045 168.0453 -0.0045 -100.7977 -0.0045 -31.7881 -0.0045 -43.3799 -0.0045 -87.3392 -0.0045 30.4474 -0.0045 -7.4550 -0.0045 106.5476 -0.0045 -3.9185 -0.0045 -56.8153 -0.0045 -146.7755 -0.0045 -76.6043 -0.0045 57.1774 -0.00...
output:
Same
result:
ok single line: 'Same'
Test #4:
score: -100
Wrong Answer
time: 519ms
memory: 9792kb
input:
400000 -57.6217 51.8207 -66.4301 79.8153 68.6538 169.5723 -48.0781 -6.6298 -6.7822 -17.1276 -39.4009 179.3474 63.3867 -77.7996 61.0296 23.9060 -45.3758 41.1641 70.4582 129.4273 -29.7325 -35.5175 -15.3621 31.2737 -23.1798 102.5020 80.7571 -132.1432 -48.3888 -6.5756 18.4703 135.7623 -0.8199 -65.5536 -...
output:
Different
result:
wrong answer 1st lines differ - expected: 'Same', found: 'Different'