QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#27363#2174. Which Planet is This?!Hakujitsu#WA 1594ms362020kbC++3.0kb2022-04-09 15:05:272022-04-29 05:44:24

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-29 05:44:24]
  • 评测
  • 测评结果:WA
  • 用时:1594ms
  • 内存:362020kb
  • [2022-04-09 15:05:27]
  • 提交

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

*/

Details

Tip: Click on the bar to expand more detailed information

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'