QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#512312#9168. Square Locatorucup-team133#AC ✓0ms3828kbC++232.4kb2024-08-10 14:07:542024-08-10 14:07:54

Judging History

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

  • [2024-08-10 14:07:54]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3828kb
  • [2024-08-10 14:07:54]
  • 提交

answer

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif

template <class T> std::istream& operator>>(std::istream& is, std::vector<T>& v) {
    for (auto& e : v) {
        is >> e;
    }
    return is;
}

template <class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
    for (std::string_view sep = ""; const auto& e : v) {
        os << std::exchange(sep, " ") << e;
    }
    return os;
}

template <class T, class U = T> bool chmin(T& x, U&& y) {
    return y < x and (x = std::forward<U>(y), true);
}

template <class T, class U = T> bool chmax(T& x, U&& y) {
    return x < y and (x = std::forward<U>(y), true);
}

template <class T> void mkuni(std::vector<T>& v) {
    std::ranges::sort(v);
    auto result = std::ranges::unique(v);
    v.erase(result.begin(), result.end());
}

template <class T> int lwb(const std::vector<T>& v, const T& x) {
    return std::distance(v.begin(), std::ranges::lower_bound(v, x));
}

using ll = __int128_t;

using namespace std;

const ll INF = (1 << 30) - 1;

bool check(const vector<long long>& v, ll a, ll dx, ll dy) {
    if (a * a != v[0]) return false;
    ll x = 0, y = a;
    for (int i = 1; i < 4; i++) {
        x += dx;
        y += dy;
        swap(dx, dy);
        dx *= -1;
        if (x * x + y * y != v[i]) return false;
    }
    return true;
}

ll SQRT(ll n) {
    ll lb = 0, ub = INF;
    while (ub - lb > 1) {
        ll mid = (lb + ub) >> 1;
        (mid * mid <= n ? lb : ub) = mid;
    }
    return lb;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    vector<long long> v(4);
    cin >> v;

    ll a = SQRT(v[0]);
    assert((v[3] - v[1]) % (2 * a) == 0);
    ll diff = (v[3] - v[1]) / (2 * a);                       // dx - dy
    ll A = 2, B = a - diff, C = a * a + diff * diff - v[3];  // A (dx)^2 + 2 B dx + C = 0
    ll D = B * B - A * C;
    assert(D >= 0);
    D = SQRT(D);
    for (int _ = 0; _ < 2; _++, D *= -1) {
        ll dx = (-B + D) / 2, dy = dx - diff;
        if (check(v, a, dx, dy)) {
            long long x = 0, y = a;
            cout << y;
            for (int i = 0; i < 3; i++) {
                x += dx;
                y += dy;
                swap(dx, dy);
                dx *= -1;
                cout << " " << x << " " << y;
            }
            cout << "\n";
            return 0;
        }
    }
    return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

36 5 10 41

output:

6 -1 2 3 1 4 5

result:

ok Answer is correct

Test #2:

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

input:

1 1 1 1

output:

1 0 1 0 1 0 1

result:

ok Answer is correct

Test #3:

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

input:

1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000

output:

1000000000 0 1000000000 0 1000000000 0 1000000000

result:

ok Answer is correct

Test #4:

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

input:

4 10 8 2

output:

2 -1 3 -2 2 -1 1

result:

ok Answer is correct

Test #5:

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

input:

4 50 104 58

output:

2 5 5 2 10 -3 7

result:

ok Answer is correct

Test #6:

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

input:

9 16 65 58

output:

3 4 0 7 4 3 7

result:

ok Answer is correct

Test #7:

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

input:

25 13 101 113

output:

5 3 -2 10 1 7 8

result:

ok Answer is correct

Test #8:

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

input:

16 25 58 49

output:

4 3 4 3 7 0 7

result:

ok Answer is correct

Test #9:

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

input:

374544 2235250 4453364 2592658

output:

612 885 1205 292 2090 -593 1497

result:

ok Answer is correct

Test #10:

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

input:

126736 551200 1838608 1414144

output:

356 732 -124 1212 608 480 1088

result:

ok Answer is correct

Test #11:

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

input:

6007401 6936277 5051405 4122529

output:

2451 -426 2599 -574 2173 -148 2025

result:

ok Answer is correct

Test #12:

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

input:

2209 2536706 4875777 2341280

output:

47 -691 1435 -2079 744 -1388 -644

result:

ok Answer is correct

Test #13:

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

input:

986962771600 2474826790757 5529645464114 4041781444957

output:

993460 1005254 1210079 788635 2215333 -216619 1998714

result:

ok Answer is correct

Test #14:

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

input:

722790729241 782340801290 3904082690373 3844532618324

output:

850171 881809 -68947 1800927 812862 919118 1731980

result:

ok Answer is correct

Test #15:

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

input:

3870332944 287487526720 654504136912 370886943136

output:

62212 530544 -77528 670284 453016 139740 592756

result:

ok Answer is correct

Test #16:

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

input:

42230661001 2038831296200 3308981375377 1312380740178

output:

205501 -771514 1201498 -1767511 429984 -995997 -566013

result:

ok Answer is correct

Test #17:

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

input:

132551656347532249 102473514386838101 439829344402853445 469907486363547593

output:

364076443 285439930 144905351 504611022 430345281 219171092 649516373

result:

ok Answer is correct

Test #18:

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

input:

55636209407170681 109515374676898429 329424831462677605 275545666192949857

output:

235873291 284729573 168654810 351948054 453384383 67218481 520602864

result:

ok Answer is correct

Test #19:

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

input:

466589422796014144 325095618166198298 43553814262839476 185047618892655322

output:

683073512 -301902073 483684563 -102513124 181782490 199388949 381171439

result:

ok Answer is correct

Test #20:

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

input:

6909562468993284 229067899424048957 357610810027741258 135452473072685585

output:

83123778 -222468866 423763499 -563108587 201294633 -340639721 -139345088

result:

ok Answer is correct

Test #21:

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

input:

5000019216542596 408275955794662066 885792080806957480 482516144228838010

output:

70710814 617703405 163457821 524956398 781161226 -92747007 688414219

result:

ok Answer is correct

Test #22:

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

input:

1736111972222329 40264917317940640 105455671025820505 66926865680102194

output:

41666677 166940988 -111335636 319943301 55605352 153002313 208607665

result:

ok Answer is correct

Test #23:

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

input:

255964325056888900 56517928013623933 645740568455742866 845186965499007833

output:

505929170 234517643 -38979522 779426335 195538121 544908692 740446813

result:

ok Answer is correct

Test #24:

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

input:

477032252615296225 108870012374411737 333393233802837749 701555474043722237

output:

690675215 62389539 324002404 429062350 386391943 366672811 753064754

result:

ok Answer is correct

Test #25:

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

input:

1299556716903225 355747388532580098 692024059544933421 337576227729256548

output:

36049365 252350757 540431757 -252031635 792782514 -504382392 288400122

result:

ok Answer is correct

Test #26:

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

input:

65258206810145881 521153173952727205 930630862422604093 474735895280022769

output:

255456859 307048086 653356447 -90851502 960404533 -397899588 562504945

result:

ok Answer is correct

Test #27:

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

input:

8131402216306944 151743259973886485 212869615963839370 69257758206259829

output:

90174288 -243418711 304122658 -457367081 60703947 -213948370 -153244423

result:

ok Answer is correct

Extra Test:

score: 0
Extra Test Passed