QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#513288#9168. Square Locatorucup-team3877#AC ✓1ms3808kbC++2312.4kb2024-08-10 17:25:142024-08-10 17:25:15

Judging History

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

  • [2024-08-10 17:25:15]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3808kb
  • [2024-08-10 17:25:14]
  • 提交

answer

//line 1 "answer.cpp"
#if !__INCLUDE_LEVEL__
#include __FILE__
using lll = __int128_t;
int main() {
    vl xo(4); input(xo);
    vector<lll> x(4);
    rep(i, 4) x[i] = xo[i];
    lll ay = sqrtll(xo[0]);
    lll k = (x[1] - x[3]) / (2 * ay);
    debug((ll)ay, (ll)k);
    {
        lll ok = -((ay + k + 1) / 2);
        lll add = 1;
        debug((ll)ok);
        auto check = [&](lll x) -> bool {
            lll y = x + ay + k;
            return x * x + y * y <= xo[1];
        };
        while (true) {
            lll x = ok - add;
            if (!check(x)) { break; }
            add *= 2;
        }
        lll ng = ok - add;
        debug((ll)ok, (ll)add);
        while (ok - ng > 1) {
            lll mid = (ok + ng) / 2;
            if (check(mid)) { ok = mid; }
            else { ng = mid; }
        }
        lll x = ok;
        lll y = ok + ay + k;
        debug((ll)x, (ll)y);
        if (x * x + y * y == xo[1]) {
            lll x1 = x + (ay - y);
            lll y1 = y + x;
            lll x2 = (ay - y);
            lll y2 = ay + x;
            print((ll)ay, (ll)x, (ll)y, (ll)x1, (ll)y1, (ll)x2, (ll)y2);
            return 0;
        }
    }
    {
        lll ok = -((ay + k) / 2);
        lll add = 1;
        debug((ll)ok);
        auto check = [&](lll x) -> bool {
            lll y = x + ay + k;
            return x * x + y * y <= xo[1];
        };
        while (true) {
            lll x = ok + add;
            if (!check(x)) { break; }
            add *= 2;
        }
        lll ng = ok + add;
        debug((ll)ok, (ll)add);
        while (ok - ng > 1) {
            lll mid = (ok + ng) / 2;
            if (check(mid)) { ok = mid; }
            else { ng = mid; }
        }
        lll x = ok;
        lll y = ok + ay + k;
        debug((ll)x, (ll)y);
        if (x * x + y * y == xo[1]) {
            lll x1 = x + (ay - y);
            lll y1 = y + x;
            lll x2 = (ay - y);
            lll y2 = ay + x;
            print((ll)ay, (ll)x, (ll)y, (ll)x1, (ll)y1, (ll)x2, (ll)y2);
            return 0;
        }
    }
    assert(false);
}
#else
//line 2 "/home/seekworser/.cpp_lib/competitive_library/competitive/std/std.hpp"
#include <bits/stdc++.h>
#ifndef LOCAL_TEST
#pragma GCC target ("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#endif // LOCAL_TEST
using namespace std;
using std::cout;
// shorten typenames
using ll = long long;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using vi = vector<int>;  using vvi = vector<vi>; using vvvi = vector<vvi>;
using vl = vector<ll>;  using vvl = vector<vl>; using vvvl = vector<vvl>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
using vs = vector<string>; using vvs = vector<vector<string>>; using vvvs = vector<vector<vector<string>>>;
template<typename T> vector<vector<T>> vv(int h, int w, T val = T()) { return vector(h, vector<T>(w, val)); }
template<typename T> vector<vector<vector<T>>> vvv(int h1, int h2, int h3, T val = T()) { return vector(h1, vector(h2, vector<T>(h3, val))); }
template<typename T> vector<vector<vector<vector<T>>>> vvvv(int h1, int h2, int h3, int h4, T val = T()) { return vector(h1, vector(h2, vector(h3, vector<T>(h4, val)))); }
template <class T> using priority_queue_min = priority_queue<T, vector<T>, greater<T>>;
// define CONSTANTS
constexpr double PI = 3.14159265358979323;
constexpr int INF = 100100111; constexpr ll INFL = 3300300300300300491LL;
float EPS = 1e-8; double EPSL = 1e-10;
template<typename T> bool eq(const T x, const T y) { return x == y; }
template<> bool eq<double>(const double x, const double y) { return (abs(x - y) < EPSL * x || abs(x - y) < EPSL); }
template<> bool eq<float>(const float x, const float y) { return abs(x - y) < EPS * x; }
template<typename T> bool neq(const T x, const T y) { return !(eq<T>(x, y)); }
template<typename T> bool ge(const T x, const T y) { return (eq<T>(x, y) || (x > y)); }
template<typename T> bool le(const T x, const T y) { return (eq<T>(x, y) || (x < y)); }
template<typename T> bool gt(const T x, const T y) { return !(le<T>(x, y)); }
template<typename T> bool lt(const T x, const T y) { return !(ge<T>(x, y)); }
constexpr int MODINT998244353 = 998244353;
constexpr int MODINT1000000007 = 1000000007;
// fasten io
struct Nyan { Nyan() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } nyan;
// define macros
#define all(a) (a).begin(), (a).end()
#define sz(x) ((ll)(x).size())
#define rep1(n) for(ll dummy_iter = 0LL; dummy_iter < n; ++dummy_iter) // 0,1,...,n-1
#define rep2(i, n) for(ll i = 0LL, i##_counter = 0LL; i##_counter < ll(n); ++(i##_counter), (i) = i##_counter) // i=0,1,...,n-1
#define rep3(i, s, t) for(ll i = ll(s), i##_counter = ll(s); i##_counter < ll(t); ++(i##_counter), (i) = (i##_counter)) // i=s,s+1,...,t-1
#define rep4(i, s, t, step) for(ll i##_counter = step > 0 ? ll(s) : -ll(s), i##_end = step > 0 ? ll(t) : -ll(t), i##_step = abs(step), i = ll(s); i##_counter < i##_end; i##_counter += i##_step, i = step > 0 ? i##_counter : -i##_counter) // i=s,s+step,...,<t
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define repe(a, v) for(auto& a : (v)) // iterate over all elements in v
#define smod(n, m) ((((n) % (m)) + (m)) % (m))
#define sdiv(n, m) (((n) - smod(n, m)) / (m))
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());}
int Yes(bool b=true) { cout << (b ? "Yes\n" : "No\n"); return 0; };
int YES(bool b=true) { cout << (b ? "YES\n" : "NO\n"); return 0; };
int No(bool b=true) {return Yes(!b);};
int NO(bool b=true) {return YES(!b);};
template<typename T, size_t N> T max(array<T, N>& a) { return *max_element(all(a)); };
template<typename T, size_t N> T min(array<T, N>& a) { return *min_element(all(a)); };
template<typename T> T max(vector<T>& a) { return *max_element(all(a)); };
template<typename T> T min(vector<T>& a) { return *min_element(all(a)); };
template<typename T> vector<T> vec_slice(const vector<T>& a, int l, int r) { vector<T> rev; rep(i, l, r) rev.push_back(a[i]); return rev; };
template<typename T> T sum(vector<T>& a, T zero = T(0)) { T rev = zero; rep(i, sz(a)) rev += a[i]; return rev; };
template<typename T> bool in_range(const T& val, const T& s, const T& t) { return s <= val && val < t; };

template <class T> inline vector<T>& operator--(vector<T>& v) { repe(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repe(x, v) ++x; return v; }

ll powm(ll a, ll n, ll mod=INFL) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = (res * a) % mod;
        if (n > 1) a = (a * a) % mod;
        n >>= 1;
    }
    return res;
}
ll sqrtll(ll x) {
    assert(x >= 0);
    ll rev = sqrt(x);
    while(rev * rev > x) --rev;
    while((rev+1) * (rev+1)<=x) ++rev;
    return rev;
}
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; }
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; }
int digit(ll x, int d=10) { int rev=0; while (x > 0) { rev++; x /= d;}; return rev; }
/**
 * @brief std.hpp
 * @docs docs/std/std.md
 */
//line 3 "/home/seekworser/.cpp_lib/competitive_library/competitive/std/io.hpp"
// overload operators (prototypes)
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p);
template <class T> inline istream& operator>>(istream& is, vector<T>& v);
template <class T, class U> inline ostream& operator<<(ostream& os, const pair<T, U>& p);
template <class T> inline ostream& operator<<(ostream& os, const vector<T>& v);
template <typename T, typename S> ostream &operator<<(ostream &os, const map<T, S> &mp);
template <typename T> ostream &operator<<(ostream &os, const set<T> &st);
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st);
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &st);
template <typename T> ostream &operator<<(ostream &os, queue<T> q);
template <typename T> ostream &operator<<(ostream &os, deque<T> q);
template <typename T> ostream &operator<<(ostream &os, stack<T> st);
template <class T, class Container, class Compare> ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq);

// overload operators
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repe(x, v) is >> x; return is; }
template <class T, class U> inline ostream& operator<<(ostream& os, const pair<T, U>& p) { os << p.first << " " << p.second; return os; }
template <class T> inline ostream& operator<<(ostream& os, const vector<T>& v) { rep(i, sz(v)) { os << v.at(i); if (i != sz(v) - 1) os << " "; } return os; }
template <typename T, typename S> ostream &operator<<(ostream &os, const map<T, S> &mp) { for (auto &[key, val] : mp) { os << key << ":" << val << " "; } return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &st) { auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &st) { auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &st) { ll cnt = 0; for (auto &e : st) { os << e << (++cnt != (int)st.size() ? " " : ""); } return os; }
template <typename T> ostream &operator<<(ostream &os, queue<T> q) { while (q.size()) { os << q.front() << " "; q.pop(); } return os; }
template <typename T> ostream &operator<<(ostream &os, deque<T> q) { while (q.size()) { os << q.front(); q.pop_front(); if (q.size()) os << " "; } return os; }
template <typename T> ostream &operator<<(ostream &os, stack<T> st) { while (st.size()) { os << st.top() << " "; st.pop(); } return os; }
template <class T, class Container, class Compare> ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq) { while (pq.size()) { os << pq.top() << " "; pq.pop(); } return os; }

template <typename T> int print_sep_end(string sep, string end, const T& val) { (void)sep; cout << val << end; return 0; };
template <typename T1, typename... T2> int print_sep_end(string sep, string end, const T1 &val, const T2 &...remain) {
    cout << val << sep;
    print_sep_end(sep, end, remain...);
    return 0;
};
template <typename... T> int print(const T &...args) { print_sep_end(" ", "\n", args...); return 0; };
template <typename... T> void flush() { cout << flush; };
template <typename... T> int print_and_flush(const T &...args) { print(args...); flush(); return 0; };
#define debug(...) debug_func(0, #__VA_ARGS__, __VA_ARGS__) // debug print
template <typename T> void input(T &a) { cin >> a; };
template <typename T1, typename... T2> void input(T1&a, T2 &...b) { cin >> a; input(b...); };
#ifdef LOCAL_TEST
template <typename T> void debug_func(int i, const T name) { (void)i; (void)name; cerr << endl; }
template <typename T1, typename T2, typename... T3> void debug_func(int i, const T1 &name, const T2 &a, const T3 &...b) {
    int scope = 0;
    for ( ; (scope != 0 || name[i] != ',') && name[i] != '\0'; i++ ) {
        cerr << name[i];
        if (name[i] == '(' || name[i] == '{') scope++;
        if (name[i] == ')' || name[i] == '}') scope--;
    }
    cerr << ":" << a << " ";
    debug_func(i + 1, name, b...);
}
template <typename T1, typename T2, typename... T3> void debug_func(int i, const T1 &name, T2 &a, T3 &...b) {
    int scope = 0;
    for ( ; (scope != 0 || name[i] != ',') && name[i] != '\0'; i++ ) {
        cerr << name[i];
        if (name[i] == '(' || name[i] == '{') scope++;
        if (name[i] == ')' || name[i] == '}') scope--;
    }
    cerr << ":" << a << " ";
    debug_func(i + 1, name, b...);
}
#endif
#ifndef LOCAL_TEST
template <typename... T>
void debug_func(T &...) {}
template <typename... T>
void debug_func(const T &...) {}
#endif
/**
 * @brief io.hpp
 * @docs docs/std/io.md
 */
//line 80 "answer.cpp"
#endif

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3608kb

input:

36 5 10 41

output:

6 -2 1 3 -1 5 4

result:

ok Answer is correct

Test #2:

score: 0
Accepted
time: 1ms
memory: 3744kb

input:

1 1 1 1

output:

1 -1 0 0 -1 1 0

result:

ok Answer is correct

Test #3:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000

output:

1000000000 -1000000000 0 0 -1000000000 1000000000 0

result:

ok Answer is correct

Test #4:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

4 10 8 2

output:

2 -3 1 -2 -2 1 -1

result:

ok Answer is correct

Test #5:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

4 50 104 58

output:

2 -5 -5 2 -10 7 -3

result:

ok Answer is correct

Test #6:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

9 16 65 58

output:

3 0 -4 7 -4 7 3

result:

ok Answer is correct

Test #7:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

25 13 101 113

output:

5 2 -3 10 -1 8 7

result:

ok Answer is correct

Test #8:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

16 25 58 49

output:

4 -4 -3 3 -7 7 0

result:

ok Answer is correct

Test #9:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

374544 2235250 4453364 2592658

output:

612 -1205 -885 292 -2090 1497 -593

result:

ok Answer is correct

Test #10:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

126736 551200 1838608 1414144

output:

356 124 -732 1212 -608 1088 480

result:

ok Answer is correct

Test #11:

score: 0
Accepted
time: 0ms
memory: 3488kb

input:

6007401 6936277 5051405 4122529

output:

2451 -2599 426 -574 -2173 2025 -148

result:

ok Answer is correct

Test #12:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

2209 2536706 4875777 2341280

output:

47 -1435 691 -2079 -744 -644 -1388

result:

ok Answer is correct

Test #13:

score: 0
Accepted
time: 0ms
memory: 3736kb

input:

986962771600 2474826790757 5529645464114 4041781444957

output:

993460 -1210079 -1005254 788635 -2215333 1998714 -216619

result:

ok Answer is correct

Test #14:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

722790729241 782340801290 3904082690373 3844532618324

output:

850171 68947 -881809 1800927 -812862 1731980 919118

result:

ok Answer is correct

Test #15:

score: 0
Accepted
time: 0ms
memory: 3736kb

input:

3870332944 287487526720 654504136912 370886943136

output:

62212 77528 -530544 670284 -453016 592756 139740

result:

ok Answer is correct

Test #16:

score: 0
Accepted
time: 0ms
memory: 3508kb

input:

42230661001 2038831296200 3308981375377 1312380740178

output:

205501 -1201498 771514 -1767511 -429984 -566013 -995997

result:

ok Answer is correct

Test #17:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

132551656347532249 102473514386838101 439829344402853445 469907486363547593

output:

364076443 -144905351 -285439930 504611022 -430345281 649516373 219171092

result:

ok Answer is correct

Test #18:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

55636209407170681 109515374676898429 329424831462677605 275545666192949857

output:

235873291 -168654810 -284729573 351948054 -453384383 520602864 67218481

result:

ok Answer is correct

Test #19:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

466589422796014144 325095618166198298 43553814262839476 185047618892655322

output:

683073512 -483684563 301902073 -102513124 -181782490 381171439 199388949

result:

ok Answer is correct

Test #20:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

6909562468993284 229067899424048957 357610810027741258 135452473072685585

output:

83123778 -423763499 222468866 -563108587 -201294633 -139345088 -340639721

result:

ok Answer is correct

Test #21:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

5000019216542596 408275955794662066 885792080806957480 482516144228838010

output:

70710814 -163457821 -617703405 524956398 -781161226 688414219 -92747007

result:

ok Answer is correct

Test #22:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

1736111972222329 40264917317940640 105455671025820505 66926865680102194

output:

41666677 111335636 -166940988 319943301 -55605352 208607665 153002313

result:

ok Answer is correct

Test #23:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

255964325056888900 56517928013623933 645740568455742866 845186965499007833

output:

505929170 38979522 -234517643 779426335 -195538121 740446813 544908692

result:

ok Answer is correct

Test #24:

score: 0
Accepted
time: 0ms
memory: 3752kb

input:

477032252615296225 108870012374411737 333393233802837749 701555474043722237

output:

690675215 -324002404 -62389539 429062350 -386391943 753064754 366672811

result:

ok Answer is correct

Test #25:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

1299556716903225 355747388532580098 692024059544933421 337576227729256548

output:

36049365 -540431757 -252350757 -252031635 -792782514 288400122 -504382392

result:

ok Answer is correct

Test #26:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

65258206810145881 521153173952727205 930630862422604093 474735895280022769

output:

255456859 -653356447 -307048086 -90851502 -960404533 562504945 -397899588

result:

ok Answer is correct

Test #27:

score: 0
Accepted
time: 0ms
memory: 3752kb

input:

8131402216306944 151743259973886485 212869615963839370 69257758206259829

output:

90174288 -304122658 243418711 -457367081 -60703947 -153244423 -213948370

result:

ok Answer is correct

Extra Test:

score: 0
Extra Test Passed