QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#376636#2174. Which Planet is This?!willow#WA 177ms125180kbC++173.5kb2024-04-04 14:17:222024-04-04 14:17:23

Judging History

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

  • [2024-04-04 14:17:23]
  • 评测
  • 测评结果:WA
  • 用时:177ms
  • 内存:125180kb
  • [2024-04-04 14:17:22]
  • 提交

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()) {
// 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");
}

详细

Test #1:

score: 100
Accepted
time: 20ms
memory: 114276kb

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: 177ms
memory: 125180kb

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'