QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#376638#2174. Which Planet is This?!installb#WA 304ms30728kbC++202.4kb2024-04-04 14:20:062024-04-04 14:20:06

Judging History

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

  • [2024-04-04 14:20:06]
  • 评测
  • 测评结果:WA
  • 用时:304ms
  • 内存:30728kb
  • [2024-04-04 14:20:06]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 3600000;
const int B = 4000001;
const int P0 = 1000000007;
const int P1 = 998244353;

int n;
vector <int> va[N],vb[N];
int pB[2][N],sa[N],sb[N],hb[2][N];

bool solve(){
    cin >> n;
    for(int i = 1;i <= n;i ++){
        db x,y; cin >> x >> y;
        int cx = x * 10000 + 900000;
        int cy = y * 10000 + 1800000;
        va[cx].push_back(cy);
    }
    for(int i = 1;i <= n;i ++){
        db x,y; cin >> x >> y;
        int cx = x * 10000 + 900000;
        int cy = y * 10000 + 1800000;
        vb[cx].push_back(cy);
    }
    pB[0][0] = pB[1][0] = 1;
    for(int i = 1;i <= n + n;i ++){
        pB[0][i] = 1ll * B * pB[0][i - 1] % P0;
        pB[1][i] = 1ll * B * pB[1][i - 1] % P1;
    } 
    int num = 0;
    map <int,int> mp;
    for(int i = 0;i <= 1800000;i ++){
        if(va[i].size() != vb[i].size()) return 0;
        if(va[i].size() == 0) continue;
        num ++;
        sort(va[i].begin(),va[i].end());
        sort(vb[i].begin(),vb[i].end());

        int sz = va[i].size();
        for(int j = 1;j < sz;j ++) sa[i] = (va[i][j] - va[i][j - 1] + N) % N;
        sa[sz] = (va[i][0] - va[i].back() + N) % N;
        for(int j = 1;j < sz;j ++) sb[i] = (vb[i][j] - vb[i][j - 1] + N) % N;
        sb[sz] = (vb[i][0] - vb[i].back() + N) % N;

        for(int j = sz + 1;j <= sz + sz;j ++) sb[j] = sb[j - sz];
        for(int j = 1;j <= sz + sz;j ++){
            hb[0][j] = (hb[0][j - 1] + 1ll * pB[0][j - 1] * sb[j]) % P0;
            hb[1][j] = (hb[1][j - 1] + 1ll * pB[1][j - 1] * sb[j]) % P1;
        }
        int xa[2] = {0};
        for(int j = 1;j <= sz;j ++){
            xa[0] = (xa[0] + 1ll * pB[0][j - 1] * sa[j]) % P0;
            xa[1] = (xa[1] + 1ll * pB[1][j - 1] * sa[j]) % P1;
        }
        for(int j = 1;j <= sz;j ++){
            int xb[2] = {0};
            xb[0] = (hb[0][j + sz - 1] - hb[0][j - 1] + P0) % P0;
            xb[1] = (hb[1][j + sz - 1] - hb[1][j - 1] + P1) % P1;
            if(1ll * xa[0] * pB[0][j - 1] % P0 == xb[0] && 1ll * xa[1] * pB[1][j - 1] % P1 == xb[1])
                mp[(vb[i][j - 1] - va[i][0] + N) % N] ++;
        }
    }
    for(auto it = mp.begin();it != mp.end();it ++){
        if(it->second == num) return 1;
    }
    return 0;
}

int main(){
    ios::sync_with_stdio(false);
    cout << (solve() ? "Same" : "Different") << '\n';
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 7820kb

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: 304ms
memory: 30288kb

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: -100
Wrong Answer
time: 256ms
memory: 30728kb

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:

Different

result:

wrong answer 1st lines differ - expected: 'Same', found: 'Different'