QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#24494 | #2174. Which Planet is This?! | DaBenZhongXiaSongKuaiDi# | TL | 352ms | 31096kb | C++20 | 2.6kb | 2022-03-31 09:38:18 | 2022-04-30 05:53:45 |
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 unsigned long long 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 int bs = 15023;
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;
vector<int> match(vector<int> p, vector<int> q, int st) {
u64 pbs[maxn + 5], init = 0;
if(!init) {
init = 1;
pbs[0] = 1;
rep(i, 1, n << 1) pbs[i] = pbs[i - 1] * bs;
}
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)];
u64 ret = p[0];
rep(i, 1, sz(p) - 1) ret = ret * bs + p[i];
int qwq = st;
rep(i, 0, sz(q) - 1) {
st += p[i];
u64 cur = h[i + sz(q)] - h[i] * pbs[sz(q)];
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);
if(!ret) return ret = 1, ok = cur, 1;
else {
vector<int> nw;
sort(all(cur));
for(auto x : cur) {
if(binary_search(all(ok), x)) nw.pb(x);
}
swap(nw, ok);
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();
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: 0ms
memory: 5744kb
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: 352ms
memory: 31096kb
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: 290ms
memory: 25960kb
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
Time Limit Exceeded
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 -...