QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#56307 | #2174. Which Planet is This?! | UT_aka_Is# | WA | 502ms | 53748kb | C++ | 2.3kb | 2022-10-18 17:31:24 | 2022-10-18 17:31:26 |
Judging History
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");
}
详细
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'