QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#59554#2174. Which Planet is This?!losPatrons#TL 0ms0kbC++144.2kb2022-10-31 00:51:182022-10-31 00:51:19

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-31 00:51:19]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2022-10-31 00:51:18]
  • 提交

answer

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cassert>
#include <map>
#include <numeric>
#include <cstring>
#include <set>
#include <ctime>
#include <queue>
#include <cmath>
#include <iomanip>
#include <iterator>
#include <bitset>
#include <unordered_map>
#include <complex>
#include <unordered_set>
#include <chrono>
#include <random>
#include <array>
#include <functional>
#include <random>

using namespace std;

const int maxN = 800009, p10 = 10000, mod = 360 * p10;
int N, a[maxN], b[maxN], pi[maxN];
vector<int> v[180 * p10 + 10], h[180 * p10 + 10];
const bool DBG = 0;

int read(int &x) {
    char s[100], c;
    x = 0;
    scanf("%s", s + 1);
    bool sg = 0;
    int i = 1, N = strlen(s + 1);
    if (s[i] == '-')
        sg = 1, i ++;
    x = 0;
    while (i <= N) {
        if (s[i] != '.')
            x = x * 10 + s[i] - '0';
        i ++;
    }
    if (sg)
        x = -x;
    //printf("[%s]", s + 1);
    scanf("%c", &c);
}

void fail() {
    printf("Different\n");
    exit(0);
}

using ll = long long;

ll Euclid(ll a, ll b, ll &x, ll &y) {
    if (b) {
        ll d = Euclid(b, a % b, y, x);
        return y -= a / b * x, d;
    } else return x = 1, y = 0, a;
}

ll currM = 1, currR = 0;
pair<ll, ll> CRT(ll m1, ll r1, ll m2, ll r2) {
    if (DBG)
        cout << "CRT: " << m1 << " " << r1 << " with " << m2 << " " << r2 << '\n';
    ll s, t;
    ll g = Euclid(m1, m2, s, t);
    if (r1 % g != r2 % g) fail();
    ll z = (s * r2 * m1 + t * r1 * m2) % (m1 * m2);
    if (z < 0) z += m1 * m2;
    return {m1 / g * m2, z / g};
}

void solve(int delta) {
    int k = 0;
    if (DBG) {
        printf("delta=%d, [", delta);
        for (int i = 1; i <= N; i++)
            printf("%d ", a[i]);
        printf("\b] [");
        for (int i = 1; i <= N; i++)
            printf("%d ", b[i]);
        printf("\b]\n");
    }
    for (int i=2; i<=N; i++) {
        while (k != 0 && a[k + 1] != a[i])
            k = pi[k];
        k += (a[k + 1] == a[i]);
        pi[i] = k;
    }
    int per = N;
    for (int i=pi[N]; i != 0; i = pi[i])
        if (N % (N - i) == 0) {
            per = N - i;
            break;
        }
    k = 0;
    for (int i=N + 1; i<=2 * N; i++)
        b[i] = b[i - N];
    int found = -1;
    for (int i=1; i<=2 * N; i++) {
        while (k != 0 && a[k + 1] != b[i])
            k = pi[k];
        k += (a[k + 1] == b[i]);
        if (k == N) {
            found = i;
            break;
        }
    }
    if (found == -1)
        fail();
    for (int i=N + 1; i<=found; i++)
        delta += b[i];
    int perSum = 0;
    for (int i=1; i<=per; i++)
        perSum += a[i];
    assert(mod % perSum == 0);
    auto curr = CRT(currM, currR, perSum, delta);
    currM = curr.first, currR = curr.second;
}

void process(vector<int> &v, vector<int> &h) {
    sort(v.begin(), v.end());
    sort(h.begin(), h.end());
    for (int i=0; i + 1<v.size(); i++)
        a[i + 1] = v[i + 1] - v[i],
        b[i + 1] = h[i + 1] - h[i];
    N = v.size();
    a[N] = mod - v.back() + v.front();
    b[N] = mod - h.back() + h.front();
    solve((h[0] - v[0] + mod) % mod);
}

int main() {
    //freopen("../input", "r", stdin);
    //freopen("../output", "w", stdout);

    scanf("%d\n", &N);
    for (int i=1; i<=N; i++) {
        int x, y;
        read(x), x += 90 * p10;
        read(y), y += 360 * p10 - 1;
        v[x].push_back(y);
        if (DBG)
            printf("%d %d\n", x, y);
    }
    for (int i=1; i<=N; i++) {
        int x, y;
        read(x), x += 90 * p10;
        read(y), y += 360 * p10 - 1;
        h[x].push_back(y);
        if (DBG)
            printf("%d %d\n", x, y);
    }
    for (int i=0; i<=180 * p10; i++) {
        if (v[i].size() != h[i].size()) {
            if (DBG)
                printf("dif sz (%d): %d, %d\n", i, v[i].size(), h[i].size());
            fail();
        }
        if (!v[i].empty())
            process(v[i], h[i]);
    }
    printf("Same\n");
    return 0;
}

/*const int seed = time (0);
mt19937 gen (seed);
long long getRand(long long a, long long b) {return uniform_int_distribution < long long > (a, b) (gen);}*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

3
10 0
20 40
30 -15
40 -15
20 0
30 40

output:


result: