QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#227582 | #2174. Which Planet is This?! | TWTP_TCTF# | TL | 0ms | 3548kb | C++17 | 2.6kb | 2023-10-27 19:05:56 | 2023-10-27 19:05:57 |
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 n;
int freq[mod + 1];
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 < n; 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;
map<int, vector<int> > v1, v2;
for (int i = 0; i < n; i++) {
string s1, s2;
cin >> s1 >> s2;
v1[get_val(s1)].push_back(get_val(s2));
}
for (int i = 0; i < n; i++) {
string s1, s2;
cin >> s1 >> s2;
v2[get_val(s1)].push_back(get_val(s2));
}
for (auto i: v1) {
vector<int> &a = i.second;
vector<int> &b = v2[i.first];
if (a.size() != b.size()) {
cout << "Different";
return;
}
for (int i = 0; i < a.size(); i++) {
a[i] = (a[i] % mod + mod) % mod;
b[i] = (b[i] % mod + mod) % mod;
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int m = a.size();
vector<pair<int, int>> da(m), db(m);
for (int i = 0; i < m; i++) {
da[i] = {a[i], a[(i + 1) % m] - a[i]};
if (da[i].second < 0)da[i].second += mod;
db[i] = {b[i], b[(i + 1) % m] - b[i]};
if (db[i].second < 0)db[i].second += mod;
}
solve(da, db);
}
for (int i = 0; i < mod; i++) {
if (freq[i] == v1.size()) {
cout << "same";
return;
}
}
cout << "Different";
}
int main() {
IO
int t = 1;
//cin >> t;
for (int i = 1; i <= t; i++) {
//cout << "Case #" << i << ": ";
doWork();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3548kb
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...