QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#24504#2174. Which Planet is This?!DaBenZhongXiaSongKuaiDi#WA 506ms44192kbC++202.9kb2022-03-31 10:37:092022-04-30 05:54:41

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:54:41]
  • 评测
  • 测评结果:WA
  • 用时:506ms
  • 内存:44192kb
  • [2022-03-31 10:37:09]
  • 提交

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] + 3600000;
		st %= 3600000;
		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(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: 3ms
memory: 7836kb

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: 408ms
memory: 40032kb

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: 315ms
memory: 35588kb

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: 478ms
memory: 25684kb

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: 506ms
memory: 24144kb

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: 0ms
memory: 7844kb

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: 1ms
memory: 7828kb

input:

1
30 40
30 40

output:

Same

result:

ok single line: 'Same'

Test #8:

score: 0
Accepted
time: 4ms
memory: 7932kb

input:

1
30 40
30 -40

output:

Same

result:

ok single line: 'Same'

Test #9:

score: 0
Accepted
time: 4ms
memory: 7856kb

input:

1
30 40
-30 40

output:

Different

result:

ok single line: 'Different'

Test #10:

score: 0
Accepted
time: 2ms
memory: 7848kb

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: 7828kb

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: 0
Accepted
time: 4ms
memory: 8000kb

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:

Different

result:

ok single line: 'Different'

Test #13:

score: 0
Accepted
time: 4ms
memory: 7792kb

input:

5
0 10
0 130
0 -110
20 10
20 -170
0 90
0 -30
20 -150
0 -150
20 30

output:

Same

result:

ok single line: 'Same'

Test #14:

score: 0
Accepted
time: 3ms
memory: 7988kb

input:

5
10.0 0.0
10.0 180.0
10.0 1.0
30.0 17.0
30.0 34.0
10.0 0.0
10.0 180.0
10.0 1.0
30.0 -163.0
30.0 -146.0

output:

Different

result:

ok single line: 'Different'

Test #15:

score: 0
Accepted
time: 1ms
memory: 7992kb

input:

13
72.9961 72.3506
-75.0706 -131.8360
-65.0986 95.3431
13.7034 -53.1674
72.9961 -167.6494
-47.0019 -168.8687
86.2941 -146.6220
-3.9444 -0.2264
-88.4489 -136.0261
23.6639 -52.9231
72.9961 -47.6494
47.9655 -85.1859
73.1142 37.9033
-88.4489 54.6914
-75.0706 58.8815
23.6639 137.7944
72.9961 143.0681
-47...

output:

Same

result:

ok single line: 'Same'

Test #16:

score: -100
Wrong Answer
time: 475ms
memory: 44192kb

input:

400000
0.0010 -52.5186
0.0010 142.5366
0.0010 107.1999
0.0010 -84.4308
0.0010 99.3897
0.0010 -17.3592
0.0010 -179.7129
0.0010 -35.6184
0.0010 99.4698
0.0010 -128.7153
0.0010 -159.3837
0.0010 125.4024
0.0010 177.3702
0.0010 -18.7083
0.0010 4.2876
0.0010 122.5206
0.0010 19.2195
0.0010 129.5829
0.0010 ...

output:

Same

result:

wrong answer 1st lines differ - expected: 'Different', found: 'Same'