QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#227593 | #2174. Which Planet is This?! | TWTP_TCTF# | TL | 0ms | 3828kb | C++17 | 2.8kb | 2023-10-27 19:18:56 | 2023-10-27 19:18:56 |
Judging History
answer
#include<iostream>
#include <bits/stdc++.h>
#define ld long double
#define ll long long
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 2e5 + 5, mod = 360 * 10000;
int freq[mod + 5];
void solve(vector<pair<int, int> > &a, vector<pair<int, int> > &b) {
b.push_back({-1, -1});
int m = a.size();
for (auto i: a) {
b.push_back(i);
}
for (auto i: a) {
b.push_back(i);
}
int n = b.size();
vector<int> z(n);
set<int> vis;
for (int i = 1; i <= 2 * m; i++) {
while (i + z[i] < n && b[z[i]].second == b[i + z[i]].second) {
z[i]++;
}
if (z[i] == m) {
int d = b[i].first - b[0].first;
d = (d % mod + mod) % mod;
vis.insert(d);
}
}
for (auto i: vis) {
freq[i]++;
}
}
int get_val(string s) {
int n = s.size();
int idx = s.find('.');
if (idx == -1) {
s += "0000";
} else {
int rem = 4 - (s.size() - idx - 1);
s.erase(s.begin() + idx);
while (rem--) {
s += '0';
}
}
return stoi(s);
}
void doWork() {
int n;
cin >> n;
vector<pair<int, int> > v1, v2;
for (int i = 0; i < n; i++) {
string s1, s2;
cin >> s1 >> s2;
v1.push_back({get_val(s1), get_val(s2)});
}
for (int i = 0; i < n; i++) {
string s1, s2;
cin >> s1 >> s2;
v2.push_back({get_val(s1), get_val(s2)});
}
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
int cnt = 0;
for (int i = 0; i < n;) {
int j = i;
cnt++;
vector<int> a, b;
while (j < n && v1[j].first == v1[i].first) {
a.push_back(v1[j++].second);
}
j = i;
while (j < n && v2[j].first == v2[i].first) {
b.push_back(v2[j++].second);
}
if (v1[i].first != v2[i].first || (int) a.size() != (int) b.size()) {
cout << "Different";
return;
}
i = j;
int m = a.size();
vector<pair<int, int>> da(m), db(m);
for (int k = 0; k < m; k++) {
da[k] = {a[k], a[(k + 1) % m] - a[k]};
if (da[k].second < 0)da[k].second += mod;
db[k] = {b[k], b[(k + 1) % m] - b[k]};
if (db[k].second < 0)db[k].second += mod;
}
solve(da, db);
}
for (int i = 0; i < mod; i++) {
if (freq[i] == cnt) {
cout << "same";
return;
}
}
cout << "Different";
}
int main() {
IO
int t = 1;
//cin >> t;
for (int i = 1; i <= t; i++) {
//cout << "Case #" << i << ": ";
doWork();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3828kb
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
Time Limit Exceeded
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...