QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#370241 | #2174. Which Planet is This?! | distant_yesterday | RE | 1057ms | 188732kb | C++14 | 3.5kb | 2024-03-28 23:22:57 | 2024-03-28 23:22:58 |
Judging History
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