QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#376643#2174. Which Planet is This?!willow#WA 382ms132156kbC++173.6kb2024-04-04 14:23:592024-04-04 14:24:00

Judging History

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

  • [2024-04-04 14:24:00]
  • 评测
  • 测评结果:WA
  • 用时:382ms
  • 内存:132156kb
  • [2024-04-04 14:23:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int base1 = 19260817, base2 = 919260817, mod1 = 998244353, mod2 = 1e9 + 9;
int Add(int x, int y, int mod) {
    return (x += y) >= mod ? x - mod : x;
}
int Sub(int x, int y, int mod) {
    return (x -= y) < 0 ? x + mod : x;
}
int Mul(int x, int y, int mod) {
    return 1ll * x * y % mod;
}
int Pow(int x, int y, int mod) {
    int res = 1;
    for(; y; x = Mul(x, x, mod), y >>= 1)
        if(y & 1)
            res = Mul(res, x, mod);
    return res;
}
typedef pair<int, int> pii;
pii base = {base1, base2};
#define x first
#define y second
pii operator + (pii a, pii b) {
    return {Add(a.x, b.x, mod1), Add(a.y, b.y, mod2)};
}
pii operator - (pii a, pii b) {
    return {Sub(a.x, b.x, mod1), Sub(a.y, b.y, mod2)};
}
pii operator * (pii a, pii b) {
    return {Mul(a.x, b.x, mod1), Mul(a.y, b.y, mod2)};
}
#undef x
#undef y
const int maxn = 8e5 + 5, maxl = 2e6 + 5;
pii pw[maxn], ipw[maxn], h1[maxn];
int n, dif1[maxn], dif2[maxn];
vector<int> pos1[maxl], pos2[maxl];
set<int> now;
int main() {
    n = 8e5;
    pw[0] = {1, 1};
    for(int i = 1; i <= n; ++ i) {
        pw[i] = pw[i - 1] * base;
    }
    ipw[n].first = Pow(pw[n].first, mod1 - 2, mod1);
    ipw[n].second = Pow(pw[n].second, mod2 - 2, mod2);
    for(int i = n; i; -- i) {
        ipw[i - 1] = ipw[i] * base;
// assert(pw[i] * ipw[i] == make_pair(1, 1));
// cerr << (pw[i] * ipw[i]).first << " " << (pw[i] * ipw[i]).second << endl;
    }
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i) {
        double x, y;
        scanf("%lf%lf", &x, &y);
        int dx = (int)round((x + 90) * 10000);
        int dy = (int)round((y + 180) * 10000);
        pos1[dx].push_back(dy);
    }
    for(int i = 1; i <= n; ++ i) {
        double x, y;
        scanf("%lf%lf", &x, &y);
        int dx = (int)round((x + 90) * 10000);
        int dy = (int)round((y + 180) * 10000);
        pos2[dx].push_back(dy);
    }
    int all = 3600000, fst = 1;
    for(int x = 0; x < maxl; ++ x) {
        if(pos1[x].size() != pos2[x].size()) {
            puts("Different");
            return 0;
        }
        if(pos1[x].size()) {
            sort(pos1[x].begin(), pos1[x].end());
            sort(pos2[x].begin(), pos2[x].end());
// cerr << "x = " << x << "?? " << endl;
            set<int> nxt;
            nxt.clear();
            int w = pos1[x].size();
// for(int i = 0; i < w; ++ i) {
//     cerr << pos1[x][i] << " " << pos2[x][i] << endl;
// }
            pii h2 = {0, 0};
            for(int i = 0; i < w; ++ i) {
                dif1[i] = dif1[i + w] = (pos1[x][(i + 1) % w] - pos1[x][i] + all) % all;
                dif2[i] = (pos2[x][(i + 1) % w] - pos2[x][i] + all) % all;
// cerr << dif1[i] << " " << dif2[i] << endl;
                h2 = h2 + pw[i] * make_pair(dif2[i], dif2[i]);
            }
            for(int i = 0; i < 2 * w; ++ i) {
                h1[i + 1] = h1[i] + pw[i] * make_pair(dif1[i], dif1[i]);
            }
            for(int i = 0; i < w; ++ i) {
                if((h1[i + w] - h1[i]) * ipw[i] == h2) {
                    int dy = pos2[x][0] - pos1[x][i];
// cerr << "dx = " << x << " Fuck " << dy << " " << now.count(dy) << endl;
                    if(fst || now.count(dy)) {
                        // cerr << "? " << dy << endl;
                        nxt.insert(dy);
                    }
                }
            }
            swap(now, nxt);
// for(auto x : now)
//     cerr << x << " ";cerr << endl;
            fst = 0;
        }
    }
    puts(now.size() ? "Same" : "Different");
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 35ms
memory: 114564kb

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: 223ms
memory: 124972kb

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: 190ms
memory: 124392kb

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

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:

Different

result:

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