QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#24507 | #2174. Which Planet is This?! | DaBenZhongXiaSongKuaiDi# | RE | 4ms | 7852kb | C++20 | 2.8kb | 2022-03-31 10:45:45 | 2022-04-30 05:55:30 |
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 = 342321361;
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) {
rep(j, 0, sz(p) - 1) {
assert(p[i] == q[(j + i + 1) % sz(q)]);
}
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);
if(cur.empty()) return 0;
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: 4ms
memory: 7852kb
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
Dangerous Syscalls
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...