QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#370241#2174. Which Planet is This?!distant_yesterdayRE 1057ms188732kbC++143.5kb2024-03-28 23:22:572024-03-28 23:22:58

Judging History

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

  • [2024-03-28 23:22:58]
  • 评测
  • 测评结果:RE
  • 用时:1057ms
  • 内存:188732kb
  • [2024-03-28 23:22:57]
  • 提交

answer

#include <bits/stdc++.h>
#ifdef LOCAL
#include "cp_debug.h"
#else
#define debug(...) 42
#endif
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

template<typename T> void read(T &x){
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
    read(first);
    read(args...);
}
template<typename T> void write(T x) {
    if(x > 9) write(x/10);
    putchar(x%10 + '0');
}

vi pi(const basic_string<int>& s) {
    vi p(sz(s));
    rep(i,1,sz(s)) {
        int g = p[i-1];
        while (g && s[i] != s[g]) g = p[g-1];
        p[i] = g + (s[i] == s[g]);
    }
    return p;
}

vi match(const basic_string<int>& s, const basic_string<int>& pat) {
    vi p = pi(pat + 114514 + s), res;
    rep(i,sz(p)-sz(s),sz(p))
        if (p[i] == sz(pat)) res.push_back(i - 2 * sz(pat));
    return res;
}

const int CYCLE = 3600000;
void solve() {
    int n;
    read(n);
    map<int, pair<vi, vi>> mp;
    rep(i,0,n) {
        float fa, fb;
        scanf("%f%f", &fa, &fb);
        int a = int((fa + 90) * 10000 + 0.5); // (0, 9e5)
        int b = int((fb + 180) * 10000 + 0.5); // (0, 1.8e6)
        if(mp.find(a) == mp.end()) {
            mp[a] = {vi(), vi()};
        }
        mp[a].first.push_back(b);
    }
    rep(i,0,n) {
        float fa, fb;
        scanf("%f%f", &fa, &fb);
        int a = int((fa + 90) * 10000 + 0.5); // (0, 9e5)
        int b = int((fb + 180) * 10000 + 0.5) % CYCLE; // [0, 3.6e6)
        if(mp.find(a) == mp.end()) {
            mp[a] = {vi(), vi()};
        }
        mp[a].second.push_back(b);
    }
    vector<pii> keys;
    for(auto& [k, vec] : mp) {
        auto &[va, vb] = vec;
        sort(all(va));
        sort(all(vb));
        if(sz(va) != sz(vb)) {
            cout << "Different" << endl;
            return;
        }
        keys.emplace_back(sz(va), k);
    }
    int smallest_a = -1;
    sort(all(keys));
    for(auto [siz, k]: keys) {
        const auto &[va, vb] = mp[k];
        if(va != vb) {
            smallest_a = k;
            break;
        }
    }
    if(smallest_a == -1) {
        cout<<"Same"<<endl;
        return;
    }

    auto solve = [&]() -> int {
        const auto &[va, vb] = mp[smallest_a];
        debug(va, vb);
        basic_string<int> cnt1(CYCLE, 0), cnt2(CYCLE*2-1, 0);
        for(auto v: va) cnt1[v]++;
        for(auto v: vb) {
            cnt2[v]++;
            cnt2[v+CYCLE]++;
        }
        auto mc = match(cnt2, cnt1);
        assert(sz(mc) == 1 || sz(mc) == 0);
        return sz(mc) == 0 ? -1 : mc[0];
    };

    int ans = solve();
    debug(ans);
    if(ans == -1) {
        cout << "Different" << endl;
        return;
    }
    for(const auto& [k, vec]: mp) {
        const auto&[va, vb] = vec;
        vi vc = va;
        for(auto &g: vc) {
            g = (g + ans) % CYCLE;
        }
        sort(all(vc));
        if(vc != vb) {
            debug("GG", k, va, vb, vc);
            cout << "Different" << endl;
            return;
        }
    }
    cout << "Same" << endl;
}

signed main() {
    int T; T = 1;
    while(T--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3732kb

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: 254ms
memory: 132632kb

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: 207ms
memory: 132312kb

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: 0
Accepted
time: 946ms
memory: 171440kb

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:

Same

result:

ok single line: 'Same'

Test #5:

score: 0
Accepted
time: 1057ms
memory: 188732kb

input:

400000
68.6612 125.2502
-34.0056 -176.1203
5.5683 107.6629
-69.2218 30.3923
-17.2214 70.1128
56.9568 -148.7878
-23.9078 -171.1107
-65.9309 -18.4715
12.6709 95.8959
-66.6852 142.6653
-26.4513 106.4433
-79.1698 -119.5633
66.7118 128.2842
-16.2637 139.1541
79.5323 15.2026
70.8686 19.2645
-73.8376 114.2...

output:

Same

result:

ok single line: 'Same'

Test #6:

score: 0
Accepted
time: 50ms
memory: 129772kb

input:

18
2 0
2 1
3 2
6 -118
2 5
2 120
2 121
2 -119
4 122
5 123
4 3
2 4
2 124
2 125
2 -120
7 -117
2 -116
2 -115
2 0
2 1
2 121
6 122
3 2
2 120
7 123
4 3
2 4
2 124
4 -118
2 125
2 -120
2 -119
5 -117
2 5
2 -116
2 -115

output:

Different

result:

ok single line: 'Different'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

1
30 40
30 40

output:

Same

result:

ok single line: 'Same'

Test #8:

score: 0
Accepted
time: 57ms
memory: 129668kb

input:

1
30 40
30 -40

output:

Same

result:

ok single line: 'Same'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

1
30 40
-30 40

output:

Different

result:

ok single line: 'Different'

Test #10:

score: -100
Runtime Error

input:

6
20 -170
20 -50
20 70
30 -70
30 50
30 170
20 -150
30 -50
20 90
30 70
20 -30
30 -170

output:


result: