QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#91242	#1900. Octopus Game	rania__	AC ✓	2ms	3464kb	C++14	1.6kb	2023-03-27 20:54:39	2023-03-27 20:54:41

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-03-27 20:54:41]
评测

测评结果：AC
用时：2ms
内存：3464kb

查看

[2023-03-27 20:54:39]
提交

answer

#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define ll long long
#define int long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 5e5 + 7, P1 = 31, P2 = 37, mod = 1e9 + 7;

void doWork() {
    int x,y;
    cin >> x >> y;
    vector<pair<int,int>> ans;

    while(x && y)
    {
        if(abs(x) > abs(y))
        {
            int cur = x / y;
            if(abs(x - (cur + 1) * y) < abs(x - cur * y))
                ++cur;
            if(abs(x - (cur - 1) * y) < abs(x - cur * y))
                --cur;
            x -= cur * y;
            ans.push_back({1,-cur});
        }
        else
        {
            swap(x,y);
            int cur = x / y;
            if(abs(x - (cur + 1) * y) < abs(x - cur * y))
                ++cur;
            if(abs(x - (cur - 1) * y) < abs(x - cur * y))
                --cur;
            x -= cur * y;
            swap(x,y);
            ans.push_back({2,-cur});
        }
    }
    cout << ans.size() << endl;
    for(auto it : ans)
        cout << it.first << " " << it.second << endl;
}
 signed main() {
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
//    freopen("bisector.in","r",stdin);
//    freopen("bisector.out","w",stdout);
    int t = 1;
    // cout << primes.size() << endl;
    //cin >> t;
    while (t--) {
        doWork();
    }
    return 0;
}

Source code, Language: C++14

这程序好像有点Bug，我给组数据试试？

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3456kb

input:

-3 9

output:

1
2 3

result:

ok heap reached 0 count in less than 50 steps

Test #2:

score: 0

Accepted

time: 2ms

memory: 3380kb

input:

-27 57

output:

2
2 2
1 9

result:

ok heap reached 0 count in less than 50 steps

Test #3:

score: 0

Accepted

time: 2ms

memory: 3344kb

input:

56 15

output:

result:

ok heap reached 0 count in less than 50 steps

Test #4:

score: 0

Accepted

time: 2ms

memory: 3380kb

input:

6 -2

output:

1
1 3

result:

ok heap reached 0 count in less than 50 steps

Test #5:

score: 0

Accepted

time: 2ms

memory: 3420kb

input:

-84 57

output:

result:

ok heap reached 0 count in less than 50 steps

Test #6:

score: 0

Accepted

time: 2ms

memory: 3332kb

input:

-648 -315

output:

result:

ok heap reached 0 count in less than 50 steps

Test #7:

score: 0

Accepted

time: 2ms

memory: 3424kb

input:

4418 -527

output:

result:

ok heap reached 0 count in less than 50 steps

Test #8:

score: 0

Accepted

time: 2ms

memory: 3460kb

input:

55796 83094

output:

result:

ok heap reached 0 count in less than 50 steps

Test #9:

score: 0

Accepted

time: 0ms

memory: 3376kb

input:

581706 382159

output:

result:

ok heap reached 0 count in less than 50 steps

Test #10:

score: 0

Accepted

time: 2ms

memory: 3356kb

input:

-1570717 -5452307

output:

result:

ok heap reached 0 count in less than 50 steps

Test #11:

score: 0

Accepted

time: 2ms

memory: 3388kb

input:

35296299 62120456

output:

result:

ok heap reached 0 count in less than 50 steps

Test #12:

score: 0

Accepted

time: 0ms

memory: 3360kb

input:

133453354 276321715

output:

result:

ok heap reached 0 count in less than 50 steps

Test #13:

score: 0

Accepted

time: 0ms

memory: 3364kb

input:

4087302427 739712346

output:

result:

ok heap reached 0 count in less than 50 steps

Test #14:

score: 0

Accepted

time: 1ms

memory: 3460kb

input:

30857859855 -36651946276

output:

result:

ok heap reached 0 count in less than 50 steps

Test #15:

score: 0

Accepted

time: 1ms

memory: 3384kb

input:

290684430189 -337396975722

output:

result:

ok heap reached 0 count in less than 50 steps

Test #16:

score: 0

Accepted

time: 2ms

memory: 3456kb

input:

4018564636210 2812471427308

output:

result:

ok heap reached 0 count in less than 50 steps

Test #17:

score: 0

Accepted

time: 2ms

memory: 3364kb

input:

46017810015419 -48982225298334

output:

result:

ok heap reached 0 count in less than 50 steps

Test #18:

score: 0

Accepted

time: 2ms

memory: 3336kb

input:

-791828028554116 -417054265497197

output:

result:

ok heap reached 0 count in less than 50 steps

Test #19:

score: 0

Accepted

time: 0ms

memory: 3464kb

input:

9958409834380717 -5355316404922545

output:

result:

ok heap reached 0 count in less than 50 steps

Test #20:

score: 0

Accepted

time: 2ms

memory: 3384kb

input:

73118300939404300 -89660288210986608

output:

result:

ok heap reached 0 count in less than 50 steps

Test #21:

score: 0

Accepted

time: 2ms

memory: 3352kb

input:

-698819961200024568 438960282374739748

output:

result:

ok heap reached 0 count in less than 50 steps

Test #22:

score: 0

Accepted

time: 2ms

memory: 3356kb

input:

1 3

output:

1
2 -3

result:

ok heap reached 0 count in less than 50 steps

Test #23:

score: 0

Accepted

time: 0ms

memory: 3356kb

input:

-89 144

output:

result:

ok heap reached 0 count in less than 50 steps

Test #24:

score: 0

Accepted

time: 1ms

memory: 3360kb

input:

10946 -17711

output:

result:

ok heap reached 0 count in less than 50 steps

Test #25:

score: 0

Accepted

time: 0ms

memory: 3332kb

input:

2178309 1346269

output:

result:

ok heap reached 0 count in less than 50 steps

Test #26:

score: 0

Accepted

time: 0ms

memory: 3464kb

input:

-1346269 679891637638612258

output:

6
2 505019158607
1 -18
2 18
1 -18
2 18
1 -13

result:

ok heap reached 0 count in less than 50 steps

Test #27:

score: 0

Accepted

time: 0ms

memory: 3400kb

input:

365435296162 225851433717

output:

result:

ok heap reached 0 count in less than 50 steps

Test #28:

score: 0

Accepted

time: 1ms

memory: 3456kb

input:

225851433717 -679891637638612258

output:

result:

ok heap reached 0 count in less than 50 steps

Test #29:

score: 0

Accepted

time: 2ms

memory: 3460kb

input:

23416728348467685 14472334024676221

output:

result:

ok heap reached 0 count in less than 50 steps

Test #30:

score: 0

Accepted

time: 1ms

memory: 3360kb

input:

-23416728348467685 -37889062373143906

output:

result:

ok heap reached 0 count in less than 50 steps

Test #31:

score: 0

Accepted

time: 2ms

memory: 3380kb

input:

160500643816367088 -420196140727489673

output:

result:

ok heap reached 0 count in less than 50 steps

Test #32:

score: 0

Accepted

time: 2ms

memory: 3356kb

input:

-679891637638612258 420196140727489673

output:

result:

ok heap reached 0 count in less than 50 steps

Test #33:

score: 0

Accepted

time: 2ms

memory: 3364kb

input:

420196140727489673 679891637638612258

output:

result:

ok heap reached 0 count in less than 50 steps

Test #34:

score: 0

Accepted

time: 2ms

memory: 3332kb

input:

1000000000000000000 32

output:

1
1 -31250000000000000

result:

ok heap reached 0 count in less than 50 steps

Test #35:

score: 0

Accepted

time: 0ms

memory: 3352kb

input:

128 -1000000000000000000

output:

1
2 7812500000000000

result:

ok heap reached 0 count in less than 50 steps

Test #36:

score: 0

Accepted

time: 2ms

memory: 3460kb

input:

225851433717 591286729879

output:

result:

ok heap reached 0 count in less than 50 steps

Test #37:

score: 0

Accepted

time: 2ms

memory: 3376kb

input:

14472334024676221 8944394323791464

output:

result:

ok heap reached 0 count in less than 50 steps

Test #38:

score: 0

Accepted

time: 0ms

memory: 3360kb

input:

-1000000000000000000 1000000000000000000

output:

1
2 1

result:

ok heap reached 0 count in less than 50 steps

Test #39:

score: 0

Accepted

time: 2ms

memory: 3460kb

input:

-679891637638612256 420196140727489673

output:

result:

ok heap reached 0 count in less than 50 steps

Test #40:

score: 0

Accepted

time: 2ms

memory: 3364kb

input:

-5527939700884765 14472334024676228

output:

result:

ok heap reached 0 count in less than 50 steps