QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#24504 | #2174. Which Planet is This?! | DaBenZhongXiaSongKuaiDi# | WA | 506ms | 44192kb | C++20 | 2.9kb | 2022-03-31 10:37:09 | 2022-04-30 05:54:41 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i ++)
#define per(i, r, l) for(int i = (r); i >= (l); i --)
#define trv(i, u, v) for(int i = head[u], v = e[i].to; i; v = e[i = e[i].nxt].to)
#define fi first
#define se second
#define all(s) s.begin(), s.end()
#define sz(s) (int)(s.size())
#define lb(s) ((s) & -(s))
#define pb push_back
using namespace std;
typedef long long ll;
typedef __int128 u64;
typedef pair<int, int> P;
mt19937_64 hua(time(0));
template<typename T> inline bool chkmx(T &x, T y) {return x < y ? x = y, 1 : 0;}
template<typename T> inline bool chkmn(T &x, T y) {return y < x ? x = y, 1 : 0;}
const int maxn = 8e5;
const u64 mod = 9999999999989;
const int bs = 3650701;
int n;
struct Node {
int x, y;
void input() {
double _x, _y;
scanf("%lf%lf", &_x, &_y);
x = (_x < 0 ? _x * 1e4 - 1e-5 : _x * 1e4 + 1e-5);
y = (_y < 0 ? _y * 1e4 - 1e-5 : _y * 1e4 + 1e-5);
}
}a[maxn + 5], b[maxn + 5];
vector<int> ok;
int ret;
u64 pbs[maxn + 5];
vector<int> match(vector<int> p, vector<int> q, int st) {
vector<int> ans;
vector<u64> h(sz(q) << 1);
h[0] = q[0];
rep(i, 1, sz(h) - 1) h[i] = (h[i - 1] * bs + q[i % sz(q)]) % mod;
u64 ret = p[0];
rep(i, 1, sz(p) - 1) ret = (ret * bs + p[i]) % mod;
rep(i, 0, sz(q) - 1) {
st -= q[i] + 3600000;
st %= 3600000;
u64 cur = (h[i + sz(q)] - h[i] * pbs[sz(q)] % mod + mod) % mod;
if(cur == ret) {
ans.pb(st % 3600000);
}
}
return ans;
}
bool chk(int l, int r) {
vector<int> p, q;
rep(i, l + 1, r) p.pb(a[i].y - a[i - 1].y);
p.pb(a[l].y + 3600000 - a[r].y);
rep(i, l + 1, r) q.pb(b[i].y - b[i - 1].y);
q.pb(b[l].y + 3600000 - b[r].y);
vector<int> cur = match(p, q, a[l].y - b[l].y + 3600000);
// cout << "______" << l <<' ' << r << '\n';
// rep(i, l, r) cout << a[i].x << ' ' << a[i].y << '\n';
// rep(i, l, r) cout << b[i].x << ' ' << b[i].y << '\n';
// for(auto x : cur) cout << x <<' '; cout << '\n';
if(!ret) return ret = 1, ok = cur, 1;
else {
vector<int> nw;
sort(all(cur));
for(auto x : ok) {
if(binary_search(all(cur), x)) nw.pb(x);
}
swap(nw, ok);
// for(auto x : nw) cout << x << ' ' ; cout << '\n';
// for(auto x : ok) cout << x << ' ' ; cout << '\n';
if(ok.empty()) return 0;
return 1;
}
}
int main() {
//freopen("in.txt", "r", stdin);
scanf("%d", &n);
rep(i, 1, n) a[i].input();
rep(i, 1, n) b[i].input();
pbs[0] = 1;
rep(i, 1, n << 1) pbs[i] = pbs[i - 1] * bs % mod;
int st = clock();
auto cmp = [&] (Node x, Node y) {return x.x == y.x ? x.y < y.y : x.x < y.x;};
sort(a + 1, a + n + 1, cmp);
sort(b + 1, b + n + 1, cmp);
int flag = 1;
for(int l = 1, r; l <= n; l = r) {
r = l;
while(r <= n && a[r].x == a[l].x) r ++;
rep(i, l + 1, r - 1) {
if(b[i].x != b[l].x) flag = 0;
}
flag &= b[l].x == a[l].x;
flag &= r > n || b[r].x != b[l].x;
flag &= chk(l, r - 1);
}
cout << (flag ? "Same" : "Different") << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 7836kb
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: 408ms
memory: 40032kb
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: 315ms
memory: 35588kb
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: 0
Accepted
time: 478ms
memory: 25684kb
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:
Same
result:
ok single line: 'Same'
Test #5:
score: 0
Accepted
time: 506ms
memory: 24144kb
input:
400000 68.6612 125.2502 -34.0056 -176.1203 5.5683 107.6629 -69.2218 30.3923 -17.2214 70.1128 56.9568 -148.7878 -23.9078 -171.1107 -65.9309 -18.4715 12.6709 95.8959 -66.6852 142.6653 -26.4513 106.4433 -79.1698 -119.5633 66.7118 128.2842 -16.2637 139.1541 79.5323 15.2026 70.8686 19.2645 -73.8376 114.2...
output:
Same
result:
ok single line: 'Same'
Test #6:
score: 0
Accepted
time: 0ms
memory: 7844kb
input:
18 2 0 2 1 3 2 6 -118 2 5 2 120 2 121 2 -119 4 122 5 123 4 3 2 4 2 124 2 125 2 -120 7 -117 2 -116 2 -115 2 0 2 1 2 121 6 122 3 2 2 120 7 123 4 3 2 4 2 124 4 -118 2 125 2 -120 2 -119 5 -117 2 5 2 -116 2 -115
output:
Different
result:
ok single line: 'Different'
Test #7:
score: 0
Accepted
time: 1ms
memory: 7828kb
input:
1 30 40 30 40
output:
Same
result:
ok single line: 'Same'
Test #8:
score: 0
Accepted
time: 4ms
memory: 7932kb
input:
1 30 40 30 -40
output:
Same
result:
ok single line: 'Same'
Test #9:
score: 0
Accepted
time: 4ms
memory: 7856kb
input:
1 30 40 -30 40
output:
Different
result:
ok single line: 'Different'
Test #10:
score: 0
Accepted
time: 2ms
memory: 7848kb
input:
6 20 -170 20 -50 20 70 30 -70 30 50 30 170 20 -150 30 -50 20 90 30 70 20 -30 30 -170
output:
Same
result:
ok single line: 'Same'
Test #11:
score: 0
Accepted
time: 4ms
memory: 7828kb
input:
4 10 32.0014 10 32.0016 -10 -65.0122 0 -131.009 10 -152.8873 -10 110.0989 10 -152.8875 0 44.1021
output:
Same
result:
ok single line: 'Same'
Test #12:
score: 0
Accepted
time: 4ms
memory: 8000kb
input:
4 10 32.0014 10 32.0016 -10 -65.0123 0 -131.009 10 -152.8873 -10 110.0989 10 -152.8875 0 44.1021
output:
Different
result:
ok single line: 'Different'
Test #13:
score: 0
Accepted
time: 4ms
memory: 7792kb
input:
5 0 10 0 130 0 -110 20 10 20 -170 0 90 0 -30 20 -150 0 -150 20 30
output:
Same
result:
ok single line: 'Same'
Test #14:
score: 0
Accepted
time: 3ms
memory: 7988kb
input:
5 10.0 0.0 10.0 180.0 10.0 1.0 30.0 17.0 30.0 34.0 10.0 0.0 10.0 180.0 10.0 1.0 30.0 -163.0 30.0 -146.0
output:
Different
result:
ok single line: 'Different'
Test #15:
score: 0
Accepted
time: 1ms
memory: 7992kb
input:
13 72.9961 72.3506 -75.0706 -131.8360 -65.0986 95.3431 13.7034 -53.1674 72.9961 -167.6494 -47.0019 -168.8687 86.2941 -146.6220 -3.9444 -0.2264 -88.4489 -136.0261 23.6639 -52.9231 72.9961 -47.6494 47.9655 -85.1859 73.1142 37.9033 -88.4489 54.6914 -75.0706 58.8815 23.6639 137.7944 72.9961 143.0681 -47...
output:
Same
result:
ok single line: 'Same'
Test #16:
score: -100
Wrong Answer
time: 475ms
memory: 44192kb
input:
400000 0.0010 -52.5186 0.0010 142.5366 0.0010 107.1999 0.0010 -84.4308 0.0010 99.3897 0.0010 -17.3592 0.0010 -179.7129 0.0010 -35.6184 0.0010 99.4698 0.0010 -128.7153 0.0010 -159.3837 0.0010 125.4024 0.0010 177.3702 0.0010 -18.7083 0.0010 4.2876 0.0010 122.5206 0.0010 19.2195 0.0010 129.5829 0.0010 ...
output:
Same
result:
wrong answer 1st lines differ - expected: 'Different', found: 'Same'