QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#384925 | #2174. Which Planet is This?! | Kevin5307# | WA | 893ms | 82156kb | C++23 | 2.2kb | 2024-04-10 13:52:46 | 2024-04-10 13:52:47 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
const ll Round=360*10000;
map<int,vector<int>> vec1,vec2;
map<int,int> val;
ll C[11][11];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
for(int i=0;i<11;i++)
C[i][i]=C[i][0]=1;
for(int i=0;i<11;i++)
for(int j=1;j<i;j++)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%Round;
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
double x,y;
cin>>x>>y;
int xx=floor(x*10000+0.1);
int yy=floor(y*10000+0.1);
vec1[xx].pb(yy);
}
for(int i=1;i<=n;i++)
{
double x,y;
cin>>x>>y;
int xx=floor(x*10000+0.1);
int yy=floor(y*10000+0.1);
vec2[xx].pb(yy);
}
for(auto pr:vec1)
{
vector<int> v1=pr.second,v2=vec2[pr.first];
if(sz(v1)!=sz(v2)) die("Different");
vector<int> pool;
for(auto x:v2)
pool.pb((x+Round+Round-v1[0])%Round);
srt(pool);
uni(pool);
static ll s[11],s2[11];
memset(s,0,sizeof(s));
memset(s2,0,sizeof(s2));
for(auto x:v1)
{
ll val=(x+Round)%Round;
ll tmp=1;
for(int i=0;i<11;i++)
{
s[i]=(s[i]+tmp)%Round;
tmp=tmp*val%Round;
}
}
for(auto x:v2)
{
ll val=(x+Round)%Round;
ll tmp=1;
for(int i=0;i<11;i++)
{
s2[i]=(s2[i]+tmp)%Round;
tmp=tmp*val%Round;
}
}
for(auto delta:pool)
{
bool ok=1;
for(int i=0;i<11;i++)
{
ll reals=0;
ll pw=1;
for(int j=0;j<=i;j++,pw=pw*delta%Round)
reals=(reals+pw*s[i-j]%Round*C[i][j])%Round;
if(reals!=s2[i])
ok=0;
}
if(ok)
val[delta]++;
}
}
for(auto pr:val)
if(pr.second==sz(vec1))
die("Same");
die("Different");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3800kb
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: 330ms
memory: 13364kb
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: 276ms
memory: 12336kb
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: 815ms
memory: 59160kb
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: 893ms
memory: 82156kb
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: 3724kb
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: 0ms
memory: 3704kb
input:
1 30 40 30 40
output:
Same
result:
ok single line: 'Same'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
1 30 40 30 -40
output:
Same
result:
ok single line: 'Same'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
1 30 40 -30 40
output:
Different
result:
ok single line: 'Different'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3932kb
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: 0ms
memory: 3796kb
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: 0ms
memory: 3956kb
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: 0ms
memory: 3752kb
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: 0ms
memory: 3728kb
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: 0ms
memory: 3712kb
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: 0
Accepted
time: 366ms
memory: 14120kb
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:
Different
result:
ok single line: 'Different'
Test #17:
score: 0
Accepted
time: 338ms
memory: 13352kb
input:
360000 0.0010 86.2510 0.0010 -5.0430 0.0010 -78.6590 0.0010 88.4350 0.0010 61.5670 0.0010 -24.3550 0.0010 -115.3940 0.0010 -146.3440 0.0010 124.0460 0.0010 127.3520 0.0010 -4.4320 0.0010 -70.2710 0.0010 14.6520 0.0010 -103.6860 0.0010 -50.1490 0.0010 -22.0840 0.0010 94.9700 0.0010 -119.5820 0.0010 -...
output:
Different
result:
ok single line: 'Different'
Test #18:
score: 0
Accepted
time: 269ms
memory: 12248kb
input:
300000 0.0010 -128.5368 0.0010 -39.3384 0.0010 162.6036 0.0010 -149.8488 0.0010 -148.3068 0.0010 -177.7872 0.0010 -31.8900 0.0010 -151.1988 0.0010 -175.1988 0.0010 43.1448 0.0010 127.7448 0.0010 149.1168 0.0010 -142.4796 0.0010 -157.0860 0.0010 166.8096 0.0010 161.9016 0.0010 53.7384 0.0010 166.9800...
output:
Different
result:
ok single line: 'Different'
Test #19:
score: 0
Accepted
time: 374ms
memory: 14068kb
input:
399998 0.0010 169.1433 0.0010 -133.3692 0.0010 -143.5779 0.0010 124.1766 0.0010 -50.3649 0.0010 110.3769 0.0010 156.5838 0.0010 -131.4630 0.0010 86.7015 0.0010 -17.1639 0.0010 -31.5108 0.0010 80.7093 0.0010 -130.5900 0.0010 74.1096 0.0010 -69.6429 0.0010 73.4841 0.0010 -103.6080 0.0010 -122.2299 0.0...
output:
Different
result:
ok single line: 'Different'
Test #20:
score: 0
Accepted
time: 342ms
memory: 13440kb
input:
359998 0.0010 -158.7000 0.0010 102.4600 0.0010 166.6080 0.0010 -101.2820 0.0010 5.1010 0.0010 48.8260 0.0010 -31.3110 0.0010 45.1100 0.0010 4.2740 0.0010 137.0020 0.0010 -155.8580 0.0010 24.9740 0.0010 134.0870 0.0010 24.5950 0.0010 -178.8530 0.0010 161.6720 0.0010 8.8610 0.0010 96.8640 0.0010 -46.9...
output:
Different
result:
ok single line: 'Different'
Test #21:
score: 0
Accepted
time: 267ms
memory: 12424kb
input:
299998 0.0010 -63.0204 0.0010 80.8788 0.0010 31.0608 0.0010 -52.0572 0.0010 -98.5944 0.0010 42.2892 0.0010 179.1996 0.0010 132.8964 0.0010 -21.2040 0.0010 120.5292 0.0010 -89.2548 0.0010 142.6236 0.0010 -178.1028 0.0010 177.5448 0.0010 -75.3084 0.0010 -69.4728 0.0010 -69.9564 0.0010 82.1208 0.0010 -...
output:
Different
result:
ok single line: 'Different'
Test #22:
score: 0
Accepted
time: 367ms
memory: 14024kb
input:
399998 -0.0045 -48.4089 -0.0045 147.2919 -0.0045 16.6727 -0.0045 150.7655 -0.0045 125.0071 -0.0045 -50.2921 -0.0045 99.7191 -0.0045 170.1879 -0.0045 -5.1185 -0.0045 69.4951 -0.0045 -45.5145 -0.0045 -14.3521 -0.0045 -88.9281 -0.0045 -107.3529 -0.0045 30.9047 -0.0045 -57.5065 -0.0045 -74.6433 -0.0045 ...
output:
Same
result:
ok single line: 'Same'
Test #23:
score: 0
Accepted
time: 362ms
memory: 14032kb
input:
400000 88.0489 2.9744 88.0489 -22.6390 88.0489 -123.9128 88.0489 138.7022 88.0489 154.1029 88.0489 -168.0274 88.0489 161.3239 88.0489 -37.7403 88.0489 -167.3690 88.0489 -99.3816 88.0489 -56.7688 88.0489 143.2672 88.0489 72.9092 88.0489 68.6632 88.0489 -157.1056 88.0489 140.0219 88.0489 -68.0880 88.0...
output:
Same
result:
ok single line: 'Same'
Test #24:
score: 0
Accepted
time: 415ms
memory: 8356kb
input:
400000 69.7815 28.3077 -9.8027 -143.2009 -34.5262 -138.8255 -68.0482 -22.1179 28.0231 3.9887 0.1627 121.6788 -37.3496 -137.1939 13.3958 -158.5526 -7.6609 124.5201 19.8342 -175.3284 -23.7926 -119.2642 78.5033 165.9076 7.7840 -114.3775 -0.6829 -84.0185 53.0080 171.7218 78.7983 57.5884 56.3950 -101.513...
output:
Same
result:
ok single line: 'Same'
Test #25:
score: 0
Accepted
time: 429ms
memory: 15348kb
input:
400000 -5.3766 -179.1860 31.9484 -165.7072 -50.7681 23.3474 13.6632 -30.0734 13.6632 2.4130 -14.5221 54.7029 -67.2466 138.7441 48.1225 145.1357 -5.3766 83.3620 31.9484 -91.8172 21.6970 -63.7793 56.0637 -53.6340 1.3936 -160.1799 31.9484 -1.1332 31.9484 13.6808 31.9484 -131.9332 31.9484 -154.2232 -50....
output:
Same
result:
ok single line: 'Same'
Test #26:
score: 0
Accepted
time: 429ms
memory: 13796kb
input:
399999 83.5831 -87.6032 35.3178 -122.9309 35.3178 -129.0045 35.3178 -147.4237 35.3178 120.6659 71.3660 -31.8948 71.3660 29.6052 35.3178 -127.6541 35.3178 99.2963 -18.6566 39.9465 -47.7236 160.0246 -65.5659 60.3442 -38.5653 25.4022 35.3178 85.6131 35.3178 120.3139 15.5911 130.9105 -69.7966 162.9249 8...
output:
Same
result:
ok single line: 'Same'
Test #27:
score: 0
Accepted
time: 422ms
memory: 13432kb
input:
399998 63.2106 159.2233 -65.0090 81.0054 45.8368 1.4093 0.4948 163.1597 16.0804 3.5328 -53.4786 -170.7581 -88.5913 -75.9890 55.7604 110.2884 0.4948 -19.2403 -78.2526 47.8895 -78.9327 93.9728 16.9410 100.5173 55.7604 -150.3241 -63.3787 -77.1591 16.9410 70.7285 -83.3175 5.2905 73.0571 -147.7457 47.662...
output:
Same
result:
ok single line: 'Same'
Test #28:
score: 0
Accepted
time: 432ms
memory: 14700kb
input:
399997 -29.8120 111.5516 5.1504 55.5098 39.5105 178.9133 44.6831 10.9492 -61.9873 -64.7071 40.1670 -157.1557 26.2250 -119.5663 36.9461 -148.6093 -0.0195 121.7616 -61.9873 73.2989 -61.9873 -179.5921 2.3796 -77.6523 26.2250 173.6321 79.6553 20.5889 -48.9698 93.5241 -48.9698 3.4341 -0.0195 47.5116 -28....
output:
Same
result:
ok single line: 'Same'
Test #29:
score: -100
Wrong Answer
time: 203ms
memory: 9824kb
input:
262144 0.0000 35.3091 0.0000 24.9300 0.0000 9.4972 0.0000 24.5530 0.0000 15.3150 0.0000 6.8275 0.0000 6.8452 0.0000 7.0695 0.0000 9.7379 0.0000 13.5652 0.0000 9.0522 0.0000 33.7650 0.0000 15.1499 0.0000 19.3118 0.0000 1.7536 0.0000 1.0710 0.0000 20.4078 0.0000 31.9173 0.0000 9.8999 0.0000 21.2611 0....
output:
Same
result:
wrong answer 1st lines differ - expected: 'Different', found: 'Same'