QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#24503 | #2174. Which Planet is This?! | DaBenZhongXiaSongKuaiDi# | WA | 527ms | 40412kb | C++20 | 2.9kb | 2022-03-31 10:30:02 | 2022-04-30 05:54:34 |
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];
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(cur.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: 7924kb
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: 410ms
memory: 40412kb
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: 364ms
memory: 35892kb
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: 498ms
memory: 24208kb
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: 527ms
memory: 24664kb
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: 4ms
memory: 7944kb
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: 3ms
memory: 7932kb
input:
1 30 40 30 40
output:
Same
result:
ok single line: 'Same'
Test #8:
score: 0
Accepted
time: 0ms
memory: 7832kb
input:
1 30 40 30 -40
output:
Same
result:
ok single line: 'Same'
Test #9:
score: 0
Accepted
time: 4ms
memory: 7924kb
input:
1 30 40 -30 40
output:
Different
result:
ok single line: 'Different'
Test #10:
score: 0
Accepted
time: 4ms
memory: 7980kb
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: 7832kb
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: -100
Wrong Answer
time: 3ms
memory: 7788kb
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:
Same
result:
wrong answer 1st lines differ - expected: 'Different', found: 'Same'