QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#512228#9168. Square Locatorucup-team987#AC ✓61ms21588kbC++203.9kb2024-08-10 13:52:422024-08-10 13:52:43

Judging History

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

  • [2024-08-10 13:52:43]
  • 评测
  • 测评结果:AC
  • 用时:61ms
  • 内存:21588kb
  • [2024-08-10 13:52:42]
  • 提交

answer

#include<iostream>
#include<algorithm>
#include<cassert>
using namespace std;
#include<iostream>
#include<vector>
#include<tuple>
#include<cmath>

template<typename Integer>
constexpr Integer sqrt_floor(const Integer& n){
    if(n <= 1)return n;
    Integer r(sqrt(n));
    do r = (r & n / r) + (r ^ n / r) / 2; while(r > n / r);
    return r;
}
template<typename Integer>
constexpr bool is_inside(const Integer& x, const Integer& y, const Integer& n){
    return (!x || x <= n / x) && (!y || y <= (n - x * x) / y);
}
template<typename Integer>
constexpr bool is_cross(const Integer& x, const Integer& y, const Integer& a, const Integer& b, const Integer& n){
    return (a * x - b * y) * (a * x - b * y) / (a * a + b * b) >= x * x + y * y - n;
}
template<typename Integer>
constexpr Integer next_in(const Integer& x, const Integer& y, const Integer& a, const Integer& b, const Integer& n){
    return (b * y - a * x - sqrt_floor((a * a + b * b) * n - (a * y + b * x) * (a * y + b * x)) + a * a + b * b - 1) / (a * a + b * b);
}
template<typename Integer>
constexpr Integer next_out(const Integer& x, const Integer& y, const Integer& a, const Integer& b, const Integer& n){
    return (b * y - a * x + sqrt_floor((a * a + b * b) * n - (a * y + b * x) * (a * y + b * x))) / (a * a + b * b);
}

void solve(){
    using namespace std;
    using integer_type = unsigned long;

    integer_type A,B,C,D;
    cin >> A >> B >> C >> D;
	integer_type N = B;

    using subtree_type = std::tuple<integer_type, integer_type, integer_type, integer_type>;
    vector<subtree_type> stern_brocot_tree{{0, 1, 1, 0}, {1, 0, 0, 0}};

    using point_type = std::pair<integer_type, integer_type>;
    vector<point_type> result{};

    point_type now_point{0, sqrt_floor(N)};

    if(now_point.second * now_point.second != N)result.emplace_back(now_point);

    while(get<0>(stern_brocot_tree.back())){
        auto& [x, y]{now_point};

        // subtree between a/b and c/d
        auto [a, b, c, d]{stern_brocot_tree.back()};
        stern_brocot_tree.pop_back();

        // next vertex of convex hull
        const auto n_upper{next_out(x, y, a, b, N)};
        x += n_upper * a;
        y -= n_upper * b;
        result.emplace_back(now_point);

        // backtrack
        while(!empty(stern_brocot_tree)){
            tie(a, b, c, d) = stern_brocot_tree.back();
            if(is_inside(x + a, y - b, N))break;
            stern_brocot_tree.pop_back();
        }

        if(empty(stern_brocot_tree))break;

        // search forward
        while(y >= d){
            if(y >= b + d && is_inside(x + a + c, y - b - d, N)){
                const auto n_lower{next_out(x + a + c, y - b - d, c, d, N)};
                tie(a, b, c, d) = make_tuple(a + c * (n_lower + 1), b + d * (n_lower + 1), a + c * (n_lower + 2), b + d * (n_lower + 2));
            }else if(is_cross(x + c, y - d, a, b, N)){
                const auto n_lower{next_in(x + c, y - d, a, b, N)};
                if(y < b * n_lower + d || !is_inside(x + a * n_lower + c, y - b * n_lower - d, N))break;
                tie(a, b, c, d) = make_tuple(a * n_lower + c, b * n_lower + d, a * (n_lower - 1) + c, b * (n_lower - 1) + d);
            }else break;
            stern_brocot_tree.emplace_back(a, b, c, d);
        }
    }

    if(now_point.second)result.emplace_back(now_point.first, 0);

	long long a=sqrt_floor(A);
	assert(a*a == A);
	//(0, a)
	auto f=[&](long long x,long long y){
		//(0, a), (x, y)
		assert(x*x+y*y==B);
		long long dx=x-0,dy=y-a;
		long long Cx=x-dy,Cy=y+dx;
		long long Dx=Cx-dx,Dy=Cy-dy;
		assert(Dx+dy==0&&Dy-dx==a);
		if(Cx*Cx+Cy*Cy==C&&Dx*Dx+Dy*Dy==D)
		{
			cout<<a<<" "<<x<<" "<<y<<" "<<Cx<<" "<<Cy<<" "<<Dx<<" "<<Dy<<endl;
			exit(0);
		}
	};

    for(const auto& [x, y] : result)if(x * x + y * y == N)
	{
		f(x,y);
		f(-x,y);
		f(x,-y);
		f(-x,-y);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
}

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

詳細信息

Test #1:

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

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: 3504kb

input:

1 1 1 1

output:

1 0 1 0 1 0 1

result:

ok Answer is correct

Test #3:

score: 0
Accepted
time: 61ms
memory: 19980kb

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: 3812kb

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: 3532kb

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: 3504kb

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: 3540kb

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: 3672kb

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: 3676kb

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: 3612kb

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: 3540kb

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: 3600kb

input:

2209 2536706 4875777 2341280

output:

47 -691 1435 -2079 744 -1388 -644

result:

ok Answer is correct

Test #13:

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

input:

986962771600 2474826790757 5529645464114 4041781444957

output:

993460 1005254 1210079 788635 2215333 -216619 1998714

result:

ok Answer is correct

Test #14:

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

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: 3768kb

input:

3870332944 287487526720 654504136912 370886943136

output:

62212 77528 -530544 670284 -453016 592756 139740

result:

ok Answer is correct

Test #16:

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

input:

42230661001 2038831296200 3308981375377 1312380740178

output:

205501 -771514 1201498 -1767511 429984 -995997 -566013

result:

ok Answer is correct

Test #17:

score: 0
Accepted
time: 33ms
memory: 11732kb

input:

132551656347532249 102473514386838101 439829344402853445 469907486363547593

output:

364076443 -144905351 -285439930 504611022 -430345281 649516373 219171092

result:

ok Answer is correct

Test #18:

score: 0
Accepted
time: 19ms
memory: 12552kb

input:

55636209407170681 109515374676898429 329424831462677605 275545666192949857

output:

235873291 -168654810 -284729573 351948054 -453384383 520602864 67218481

result:

ok Answer is correct

Test #19:

score: 0
Accepted
time: 37ms
memory: 20932kb

input:

466589422796014144 325095618166198298 43553814262839476 185047618892655322

output:

683073512 -301902073 483684563 -102513124 181782490 199388949 381171439

result:

ok Answer is correct

Test #20:

score: 0
Accepted
time: 41ms
memory: 19588kb

input:

6909562468993284 229067899424048957 357610810027741258 135452473072685585

output:

83123778 -222468866 423763499 -563108587 201294633 -340639721 -139345088

result:

ok Answer is correct

Test #21:

score: 0
Accepted
time: 41ms
memory: 21264kb

input:

5000019216542596 408275955794662066 885792080806957480 482516144228838010

output:

70710814 -163457821 -617703405 524956398 -781161226 688414219 -92747007

result:

ok Answer is correct

Test #22:

score: 0
Accepted
time: 26ms
memory: 12712kb

input:

1736111972222329 40264917317940640 105455671025820505 66926865680102194

output:

41666677 111335636 -166940988 319943301 -55605352 208607665 153002313

result:

ok Answer is correct

Test #23:

score: 0
Accepted
time: 28ms
memory: 13120kb

input:

255964325056888900 56517928013623933 645740568455742866 845186965499007833

output:

505929170 38979522 -234517643 779426335 -195538121 740446813 544908692

result:

ok Answer is correct

Test #24:

score: 0
Accepted
time: 35ms
memory: 13152kb

input:

477032252615296225 108870012374411737 333393233802837749 701555474043722237

output:

690675215 62389539 324002404 429062350 386391943 366672811 753064754

result:

ok Answer is correct

Test #25:

score: 0
Accepted
time: 44ms
memory: 21588kb

input:

1299556716903225 355747388532580098 692024059544933421 337576227729256548

output:

36049365 252350757 540431757 -252031635 792782514 -504382392 288400122

result:

ok Answer is correct

Test #26:

score: 0
Accepted
time: 54ms
memory: 20524kb

input:

65258206810145881 521153173952727205 930630862422604093 474735895280022769

output:

255456859 307048086 653356447 -90851502 960404533 -397899588 562504945

result:

ok Answer is correct

Test #27:

score: 0
Accepted
time: 26ms
memory: 11704kb

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