QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#60660#2174. Which Planet is This?!captured#WA 382ms20328kbC++174.2kb2022-11-05 22:44:572022-11-05 22:45:00

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-05 22:45:00]
  • 评测
  • 测评结果:WA
  • 用时:382ms
  • 内存:20328kb
  • [2022-11-05 22:44:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;


#define endl "\n"
#define LL long long
#define FOR(i,n) for(int i=0;i<n;i++)
#define deb(x) cerr<<#x<<" : "<<x<<" "
#define dnl cerr<<endl


const LL base[2] = {37,59};
const LL mod[2] = {(LL)1e9+7,(LL)1e9+9};
const int maxn = 4e6+40;
LL P[2][maxn];
LL H[2][maxn];
LL R[2][maxn];
LL inv[2][maxn];

inline LL power(LL a,LL b,const int m){
    if(b==0)return 1;
    if(b==1)return a%m;
    LL x = power(a,b/2,m);
    x = (x*x)%m;
    if(b%2 != 0){
        x = (x*a)%m;
    }
    return x;
}

inline LL range_hash(int idx,int l,int r){
    LL h = H[idx][r]-H[idx][l-1]+mod[idx];
    h %= mod[idx];
    if(l>0)h *= inv[idx][l-1];
    h %= mod[idx];
//    cerr<<"Shoja :";
//    deb(idx);deb(l);deb(r);deb(h);dnl;
    return h;
}
int n;
inline LL reverse_hash(int idx,int l,int r){
    LL h = R[idx][l] - R[idx][r+1] + mod[idx];
    h %= mod[idx];
    int bad = n-r;
    if(bad>0){
        h *= inv[idx][bad];
        h %= mod[idx];
    }
//    cerr<<"Ulta :";
//    deb(idx);deb(l);deb(r);deb(h);dnl;
    return h;
}

inline LL drevhash(int l,int r){
    LL x = reverse_hash(0,l,r);
    LL y = reverse_hash(1,l,r);
    return (x<<31)^y;
}

inline LL dhash(int l,int r){
    LL x = range_hash(0,l,r);
    LL y = range_hash(1,l,r);
    return (x<<31)^y;
}

int finpref(int l,int n){
    int lo=1,hi=(n-l)+1;
    hi /= 2;
    int ans = 0;

    for(int mid=lo;mid<=hi;mid++){
        if( dhash(l,l+mid-1)==drevhash(l+mid,l+mid+mid-1) ){
            ans = mid;
            return ans;
        }
    }

//    while(lo<=hi){
//        int mid = (lo+hi)>>1;
//        deb(l);deb(n);deb(mid);dnl;
//        if( dhash(l,l+mid-1)==drevhash(l+mid,l+mid+mid-1) ){
//            ans = mid;
//            lo = mid+1;
//        }
//        else hi = mid-1;
//    }
    return ans;
}

int finsuff(int l,int n){
    int lo=1,hi=(n-l)+1;
    hi /= 2;
    int ans = 0;

    for(int mid=lo;mid<=hi;mid++){
        if( dhash(n-mid+1,n)==drevhash(n-mid-mid+1,n-mid) ){
            ans = mid;
            return ans;
        }
    }
//    while(lo<=hi){
//        int mid = (lo+hi)>>1;
////        deb(mid);dnl;
//        if( dhash(n-mid+1,n)==drevhash(n-mid-mid+1,n-mid) ){
//            ans = mid;
//            lo = mid+1;
//        }
//        else hi = mid-1;
//    }
    return ans;
}



//#define cnd tree[idx]
//#define lnd idx*2,b,(b+e)/2
//#define rnd idx*2+1,(b+2)/2 + 1,e
//#define lc tree[idx*2]
//#define lr tree[idx*2+1]
//typedef pair<int,int> pii;
//struct segtree{
//    pii tree[4*maxn] ;
//    void build(int idx,int b,int e,int val){
//        cnd=pii(val,-1);
//        if(b!=e){
//            build(lnd);
//            build(rnd);
//        }
//    }
//    void update(int idx,int b,int e)
//};



void solve(int cs){
    double n, sum = 0, sum2 = 0;
    vector<double> a,b;
    cin>>n;
    for (int i = 0; i < n; i++) {
        double x, y;
        cin>>x>>y;
        sum+=y;
        a.push_back(x);
        b.push_back(y);
    }
    vector<double> a2,b2;
    for (int i = 0; i < n; i++) {
        double x, y;
        cin>>x>>y;
        sum2+=y;
        a2.push_back(x);
        b2.push_back(y);
    }
    sort(a.begin(), a.end());
    sort(a2.begin(), a2.end());
    for (int i = 0; i < n; i++) {
        if (fabs(a[i] - a2[i]) > 1e-9) {
            cout<<"Different"<<endl;
            return;
        }
    }
    sum = sum2 - sum; sum /= n;
    sort(b.begin(), b.end());
    for (int i = 0; i<n; i++) {
        b2[i] = b2[i] - sum;
        if (b2[i] > 180) {
            b2[i] -= 180;
            b2[i] = b2[i] - 180;
        }
        if (b2[i] <= -180) {
            double x = -180 - b2[i];
            b2[i] = (180 - x);

        }
    }
    sort(b2.begin(), b2.end());
    for (int i = 0; i < n; i++) {
        if (fabs(b[i] - b2[i]) > 1e-9) {
            cout<<"Different"<<endl;
            return;
        }
//        cout<<b[i]<<" "<<b2[i]<<endl;
    }
    cout<<"Same"<<endl;
}

/*
ATTAATTA

*/
int main(){

    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    int t=1;
//    cin>>t;
    for(int cs=1;cs<=t;cs++)solve(cs);
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3596kb

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

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'