QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#59555 | #2174. Which Planet is This?! | losPatrons# | RE | 0ms | 0kb | C++14 | 4.3kb | 2022-10-31 00:56:30 | 2022-10-31 00:56:30 |
Judging History
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;
cin >> (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);
}
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);
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> 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
Runtime Error
input:
3 10 0 20 40 30 -15 40 -15 20 0 30 40