QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#24494#2174. Which Planet is This?!DaBenZhongXiaSongKuaiDi#TL 352ms31096kbC++202.6kb2022-03-31 09:38:182022-04-30 05:53:45

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 05:53:45]
  • 评测
  • 测评结果:TL
  • 用时:352ms
  • 内存:31096kb
  • [2022-03-31 09:38:18]
  • 提交

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
-...

output:


result: