QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#56307#2174. Which Planet is This?!UT_aka_Is#WA 502ms53748kbC++2.3kb2022-10-18 17:31:242022-10-18 17:31:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-18 17:31:26]
  • 评测
  • 测评结果:WA
  • 用时:502ms
  • 内存:53748kb
  • [2022-10-18 17:31:24]
  • 提交

answer

#include <bits/stdc++.h>
#define SIZE 400005
#define B1 89939927
#define B2 89939929
#define M1 1000000007
#define M2 1000000009
using namespace std;
typedef long long int ll;
typedef pair <ll,ll> P;

char str[SIZE];
int A[2][SIZE],B[2][SIZE];
vector <int> vy[2][SIZE];
int get_int(){
	scanf("%s",&str);
	int L=strlen(str);
	int ret=0;
	bool up=false;
	for(int i=0;i<L;i++){
		if(str[i]=='.') continue;
		if(str[i]=='-'){
			up=true;
			continue;
		}
		ret=ret*10+(str[i]-'0');
	}
	return ret*(up?-1:1);
}
int main(){
	int n;
	scanf("%d",&n);
	vector <int> vx;
	for(int t=0;t<2;t++){
		for(int i=0;i<n;i++){
			A[t][i]=get_int(),B[t][i]=get_int();
			vx.push_back(A[t][i]);
		}
	}
	sort(vx.begin(),vx.end());
	vx.erase(unique(vx.begin(),vx.end()),vx.end());
	for(int t=0;t<2;t++){
		for(int i=0;i<n;i++){
			A[t][i]=lower_bound(vx.begin(),vx.end(),A[t][i])-vx.begin();
			vy[t][A[t][i]].push_back(B[t][i]);
		}
	}
	map <int,int> mp;
	map <int,int>::iterator it;
	for(int i=0;i<vx.size();i++){
		if(vy[0][i].size()!=vy[1][i].size()){
			puts("Different");
			return 0;
		}
		sort(vy[0][i].begin(),vy[0][i].end());
		sort(vy[1][i].begin(),vy[1][i].end());
		//printf("* %d\n",i);
		int M=3600000,sz=vy[0][i].size();
		//for(int j=0;j<sz;j++) printf("%d ",vy[0][i][j]);puts("");
		//for(int j=0;j<sz;j++) printf("%d ",vy[1][i][j]);puts("");
		vector <int> d0(sz),d1(sz);
		for(int j=0;j<sz;j++){
			int nxt=(j+1==sz?vy[0][i][0]+M:vy[0][i][j+1]);
			d0[j]=nxt-vy[0][i][j];
		}
		for(int j=0;j<sz;j++){
			int nxt=(j+1==sz?vy[1][i][0]+M:vy[1][i][j+1]);
			d1[j]=nxt-vy[1][i][j];
		}
		//for(int j=0;j<sz;j++) printf("%d ",d0[j]);puts("");
		//for(int j=0;j<sz;j++) printf("%d ",d1[j]);puts("");
		ll h1=0,h2=0;
		for(int j=0;j<sz;j++){
			h1=(h1*B1+d1[j])%M1;
			h2=(h2*B2+d1[j])%M2;
		}
		ll c1=0,c2=0,t1=1,t2=1;
		for(int j=0;j<sz;j++){
			c1=(c1*B1+d0[j])%M1;
			c2=(c2*B2+d0[j])%M2;
			t1=t1*B1%M1;
			t2=t2*B2%M2;
		}
		for(int j=0;j<sz;j++){
			c1=(c1*B1+d0[j])%M1;
			c2=(c2*B2+d0[j])%M2;
			c1=(c1-d0[j]*t1%M1+M1)%M1;
			c2=(c2-d0[j]*t2%M2+M2)%M2;
			if(P(h1,h2)==P(c1,c2)){
				int d=vy[0][i][j]-vy[1][i][sz-1];
				while(d<0) d+=M;
				while(d>=M) d-=M;
				mp[d]++;
				//printf("* %d %d : %d %d\n",i,sz,vy[0][i][j],vy[1][i][sz-1]);
			}
		}
	}
	for(it=mp.begin();it!=mp.end();it++){
		if(it->second==vx.size()){
			puts("Same");
			return 0;
		}
	}
	puts("Different");
}
		

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 22424kb

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: 201ms
memory: 36868kb

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: 173ms
memory: 34496kb

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: 429ms
memory: 47228kb

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: 502ms
memory: 53748kb

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: 2ms
memory: 22304kb

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

input:

1
30 40
30 40

output:

Same

result:

ok single line: 'Same'

Test #8:

score: 0
Accepted
time: 13ms
memory: 22300kb

input:

1
30 40
30 -40

output:

Same

result:

ok single line: 'Same'

Test #9:

score: 0
Accepted
time: 6ms
memory: 22384kb

input:

1
30 40
-30 40

output:

Different

result:

ok single line: 'Different'

Test #10:

score: -100
Wrong Answer
time: 12ms
memory: 22432kb

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:

Different

result:

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