QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#24507#2174. Which Planet is This?!DaBenZhongXiaSongKuaiDi#RE 4ms7852kbC++202.8kb2022-03-31 10:45:452022-04-30 05:55:30

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:55:30]
  • 评测
  • 测评结果:RE
  • 用时:4ms
  • 内存:7852kb
  • [2022-03-31 10:45:45]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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

output:


result: