QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94653#2174. Which Planet is This?!8BQube#WA 519ms18032kbC++202.8kb2023-04-07 14:14:542023-04-07 14:16:37

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-07 14:16:37]
  • 评测
  • 测评结果:WA
  • 用时:519ms
  • 内存:18032kb
  • [2023-04-07 14:14:54]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define pb push_back
#define ALL(v) v.begin(), v.end()

const int C = 10000;
const int AC = 360 * C;

pii arr[400005], brr[400005];

vector<int> mcp(vector<int> v, int &off) {
    int n = SZ(v), i = 0, j = 1;
    for (int k = 0; k < n; ++k)
        v.pb(v[k]);
    while (i < n && j < n) {
        int k = 0;
        while (k < n && v[i + k] == v[j + k]) ++k;
        if (v[i + k] <= v[j + k]) j += k + 1;
        else i += k + 1;
        if (i == j) ++j;
    }
    int ans = i < n ? i : j;
    off = ans;
    return vector<int>(v.begin() + ans, v.begin() + ans + n);
}

int F[400005];
void fail(vector<int> &B) {
    F[0] = -1, F[1] = 0;
    for (int i = 1, j = 0; i < SZ(B); F[++i] = ++j) {
        while (j != -1 && B[i] != B[j]) j = F[j];
    }
}

int vis[AC];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, tag = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        double a, b;
        cin >> a >> b;
        arr[i] = pii(a * C, b * C);
    }
    for (int i = 1; i <= n; ++i) {
        double a, b;
        cin >> a >> b;
        brr[i] = pii(a * C, b * C);
    }

    auto diff = [&]() {
        cout << "Different\n";
        exit(0);
    };

    auto cyc = [&](int x) {
        return (x % AC + AC) % AC;
    };

    sort(arr + 1, arr + n + 1);
    sort(brr + 1, brr + n + 1);
    for (int i = 1, j = 1; i <= n; i = j) {
        ++tag;
        while (j <= n && arr[i].X == arr[j].X) {
            if (arr[j].X != brr[j].X) diff();
            ++j;
        }
        vector<int> da, db;
        da.pb(cyc(arr[i].Y - arr[j - 1].Y));
        db.pb(cyc(brr[i].Y - brr[j - 1].Y));
        for (int k = i + 1; k < j; ++k) {
            da.pb(cyc(arr[k].Y - arr[k - 1].Y));
            db.pb(cyc(brr[k].Y - brr[k - 1].Y));
        }
        int ofa, ofb;
        mcp(da, ofa).swap(da);
        mcp(db, ofb).swap(db);
        fail(da);
        vector<int> yes;
        if (F[SZ(da)] * 2 < SZ(da) || SZ(da) % (SZ(da) - F[SZ(da)]) != 0) yes.pb(cyc(brr[i + ofb].Y - arr[i + ofa].Y));
        else {
            for (int k = 0; k < SZ(da); k += SZ(da) - F[SZ(da)])
                yes.pb(cyc(brr[i + ofb].Y - arr[(i + ofa + k) % SZ(da)].Y));
        }
        sort(ALL(yes)), yes.resize(unique(ALL(yes)) - yes.begin());
        for (int k : yes)
            ++vis[k];
        /*for (int k = 0; k < SZ(da); ++k)
            cerr << da[k] << " ";
        cerr << endl;
        for (int k = 0; k < SZ(db); ++k)
            cerr << db[k] << " ";
        cerr << endl;
        cerr << arr[i].X << ": ";
        for (int k : yes)
            cerr << k << " ";
        cerr << endl;*/
    }

    if (*max_element(vis, vis + AC) != tag) diff();
    cout << "Same\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 383ms
memory: 18032kb

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: 325ms
memory: 13980kb

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: 519ms
memory: 9792kb

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'