QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#450427 | #2174. Which Planet is This?! | evirir# | WA | 332ms | 18656kb | C++20 | 5.4kb | 2024-06-22 13:08:55 | 2024-06-22 13:08:55 |
Judging History
answer
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")
#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define cbug if(DEBUG) cout
#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
//template<typename T>
//using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
ostream& operator<<(ostream &out, ii x){ out<<"("<<x.F<<","<<x.S<<")"; return out; }
template<typename T> void amax(T &a, T b){ a=max(a,b); }
template<typename T> void amin(T &a, T b){ a=min(a,b); }
struct Hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
const ll INF = ll(1e18);
const bool DEBUG = 0;
const int MAXN = 100005;
const int LG = 21;
typedef uint64_t ull;
struct H {
ull x; H(ull x=0) : x(x) {}
H operator+(H o) { return x + o.x + (x + o.x < x); }
H operator-(H o) { return *this + ~o.x; }
H operator*(H o) { auto m = (__uint128_t)x * o.x;
return H((ull)m) + (ull)(m >> 64); }
ull get() const { return x + !~x; }
bool operator==(H o) const { return get() == o.get(); }
bool operator<(H o) const { return get() < o.get(); }
};
static const H C = (ll)1e11+3; // (order ~ 3e9; random also ok)
struct HashInterval {
vector<H> ha, pw;
HashInterval(const vector<int>& str) : ha(sz(str)+1), pw(ha) {
pw[0] = 1;
rep(i,0,sz(str))
ha[i+1] = ha[i] * C + str[i],
pw[i+1] = pw[i] * C;
}
H hashInterval(int a, int b) { // hash [a, b)
return ha[b] - ha[a] * pw[b - a];
}
};
vector<H> getHashes(const vector<int>& str, int length) {
if (sz(str) < length) return {};
H h = 0, pw = 1;
rep(i,0,length)
h = h * C + str[i], pw = pw * C;
vector<H> ret = {h};
rep(i,length,sz(str)) {
ret.push_back(h = h * C + str[i] - pw * str[i-length]);
}
return ret;
}
H hashString(const vector<int>& s){H h{}; for(auto c:s) h=h*C+c;return h;}
constexpr int MULT = 10000;
constexpr int R = 360 * MULT;
using vvi = vector<vector<int>>;
pair<vvi, vvi> read(int n, unordered_set<int, Hash>& s)
{
vector<pair<int, int>> pts;
pts.reserve(n);
vector<vector<int>> res;
forn(i,0,n)
{
ld a,b; cin>>a>>b;
a *= MULT;
b *= MULT;
int a1 = roundl(a);
a1 += 90 * MULT;
int b1 = roundl(b);
b1 += 180 * MULT - 1;
pts.pb({a1, b1});
s.insert(a1);
}
sort(all(pts));
int lastx = -1;
for (const auto& [x, y] : pts)
{
if (lastx == -1 || x != lastx) res.emplace_back();
res.back().pb(y);
lastx = x;
}
vvi res1;
res1.reserve(sz(res));
for (auto& v : res)
{
vector<int> r;
r.reserve(sz(v));
r.pb(v[0] + R - v.back());
forn(i,1,sz(v)) r.pb(v[i] - v[i - 1]);
res1.pb(r);
}
assert(sz(res) == sz(res1));
return {res, res1};
}
const string YES = "Same\n";
const string NO = "Different\n";
int main()
{
cin.tie(0)->sync_with_stdio(0);
int n; cin>>n;
unordered_set<int, Hash> sa, sb;
auto [a0, a] = read(n, sa);
auto [b0, b] = read(n, sb);
if (sa != sb)
{
cout<<NO;
return 0;
}
assert(sz(a) == sz(b));
forn(i,0,sz(a))
{
if (sz(a[i]) != sz(b[i]))
{
cout<<NO;
return 0;
}
}
vector<H> tgt;
tgt.reserve(sz(a));
for (const auto& v : a) tgt.pb(hashString(v));
vector<HashInterval> hi;
hi.reserve(sz(b));
for (const auto& v : b) hi.emplace_back(v);
unordered_set<int, Hash> offs;
forn(i,0,sz(hi))
{
auto& chi = hi[i];
unordered_set<int, Hash> coffs;
int m = sz(b[i]);
forn(off, 0, m)
{
H cur_hash = chi.hashInterval(off, m) + chi.pw[m - off] * chi.hashInterval(0, off);
if (cur_hash == tgt[i])
{
coffs.insert((a0[i][off] - b0[i][off] + R) % R);
}
}
if (i == 0)
offs = coffs;
else
{
// intersect offs and coffs
unordered_set<int, Hash> noffs;
for (const auto x : offs)
{
if (coffs.count(x)) noffs.insert(x);
}
offs = noffs;
}
if (offs.empty())
break;
}
cout << (offs.empty() ? NO : YES);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3772kb
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
Wrong Answer
time: 332ms
memory: 18656kb
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:
Different
result:
wrong answer 1st lines differ - expected: 'Same', found: 'Different'