QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#27363 | #2174. Which Planet is This?! | Hakujitsu# | WA | 1594ms | 362020kb | C++ | 3.0kb | 2022-04-09 15:05:27 | 2022-04-29 05:44:24 |
Judging History
answer
// how to come up with such solution :(
// #pragma comment(linker, "/STACK:102400000,102400000")
#pragma GCC optimize("O3")
#pragma GCC optimize("O2")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
// #pragma GCC optimize("trapv")
#include<bits/stdc++.h>
#define int long long
// #define i128 long long
#define double long double
using namespace std;
#define rep(i,n) for (int i=0;i<(int)(n);++i)
#define rep1(i,n) for (int i=1;i<=(int)(n);++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define F first
#define S second
typedef long long ll;
typedef unsigned long long ull;
// typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
int dx[]={1,1,2,2,-1,-1,-2,-2};
int dy[]={2,-2,1,-1,2,-2,1,-1};
// const int mod=1e9+7;
const int INF=LLONG_MAX;
const double EPS=1e-9;
const int N=500007;
const int K=360*10000;
const int mod[2]={998244353,234567899};
const int base[2]={12321,32123};
mt19937 rng(1234);
// int modpow(int u,int v,int mod){
// int ans=1, t=u;
// while (v){
// if (v&1) ans=ans*t%mod;
// t=t*t%mod, v>>=1;
// }
// return ans;
// }
int n;
vi lst[2][K];
int g[2][N];
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cout.precision(15), cerr.precision(15);
cin>>n;
rep(_,2){
g[_][0]=1;
for (int i=1;i<=n;++i) g[_][i]=g[_][i-1]*base[_]%mod[_];
}
rep(_,2){
rep(i,n) {
double x,y;
cin>>x>>y;
x+=90, y+=180;
int xx=x*10000, yy=y*10000;
lst[_][xx].pb(yy);
}
}
set<int> ok;
for (int i=0;i<K;++i) ok.insert(i);
for (int i=0;i<K;++i){
if (!sz(lst[0][i])) continue;
if (sz(lst[0][i])!=sz(lst[1][i])){
cout<<"Different\n";
return 0;
}
vi ok_lst;
vi &l0=lst[0][i], &l1=lst[1][i];
sort(range(l0)), sort(range(l1));
vi d0, d1;
int m=sz(l0);
rep(j,m-1) d0.pb(l0[j+1]-l0[j]);
d0.pb(l0[0]+K-l0[m-1]);
rep(j,m-1) d1.pb(l1[j+1]-l1[j]);
d1.pb(l1[0]+K-l1[m-1]);
int hsh1[2]={0,0},hsh2[2]={0,0};
rep(_,2){
rep(j,m) hsh1[_]=(hsh1[_]+d0[j]*g[_][m-j-1])%mod[_], hsh2[_]=(hsh2[_]+d1[j]*g[_][m-j-1])%mod[_];
}
int now=(l1[0]-l0[0]+K)%K;
for (int j=0;j<m;++j){
if (hsh1[0]==hsh2[0]&&hsh1[1]==hsh2[1]) ok_lst.pb(now);
now=(now+d1[j])%K;
rep(_,2) hsh2[_]=(hsh2[_]-d1[j]*g[_][m-1]%mod[_]+mod[_])%mod[_], hsh2[_]=(hsh2[_]*base[_]+d1[j])%mod[_];
}
set<int> okk;
for (auto c:ok_lst){
if (ok.find(c)!=ok.end()) okk.insert(c);
}
ok=okk;
}
if (sz(ok)) cout<<"Same";
else cout<<"Different";
return 0;
}
/*
3
0.0000 0.0000
30.0000 0.0000
30.0000 90.0000
0.0000 0.0000
30.0000 0.0000
30.0000 -90.0000
*/
详细
Test #1:
score: 100
Accepted
time: 1079ms
memory: 342916kb
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
Wrong Answer
time: 1594ms
memory: 362020kb
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:
Different
result:
wrong answer 1st lines differ - expected: 'Same', found: 'Different'