QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#450427#2174. Which Planet is This?!evirir#WA 332ms18656kbC++205.4kb2024-06-22 13:08:552024-06-22 13:08:55

Judging History

你现在查看的是最新测评结果

  • [2024-06-22 13:08:55]
  • 评测
  • 测评结果:WA
  • 用时:332ms
  • 内存:18656kb
  • [2024-06-22 13:08:55]
  • 提交

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'