QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#88339#1900. Octopus GameZuqaAC ✓3ms3488kbC++201.4kb2023-03-16 01:05:542023-03-16 01:05:56

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-16 01:05:56]
  • 评测
  • 测评结果:AC
  • 用时:3ms
  • 内存:3488kb
  • [2023-03-16 01:05:54]
  • 提交

answer

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

#define el '\n'
#define FIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef complex<ld> pt;
typedef unsigned long long ull;

template<typename T, typename X>
using hashTable = gp_hash_table<T, X>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

// mt19937_64 for long long
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());

vector<pair<int, ll>> ans;

void solve(ll a, ll b, bool f)
{
    if(!b)
        return;

    if(abs(a) < abs(b))
    {
        solve(b, a, !f);
        return;
    }

    ll k = a / b;
    if(abs(a - (k + 1) * b) < abs(a - k * b))
        k++;
    if(abs(a - (k - 1) * b) < abs(a - k * b))
        k--;

    ans.emplace_back(f, k);
    solve(a - k * b, b, f);
}

void doWork()
{
    ll a, b;
    cin >> a >> b;
    solve(a, b, 0);
    cout << ans.size() << '\n';
    for(auto &[op, k]: ans)
        cout << op + 1 << ' ' << -k << '\n';
}

signed main()
{
    FIO
    int T = 1;
//    cin >> T;
    for(int i = 1; i <= T; i++)
        doWork();
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3340kb

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

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:

3
1 -4
2 4
1 -4

result:

ok heap reached 0 count in less than 50 steps

Test #4:

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

input:

6 -2

output:

1
1 3

result:

ok heap reached 0 count in less than 50 steps

Test #5:

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

input:

-84 57

output:

3
1 1
2 2
1 9

result:

ok heap reached 0 count in less than 50 steps

Test #6:

score: 0
Accepted
time: 2ms
memory: 3372kb

input:

-648 -315

output:

3
1 -2
2 -17
1 -2

result:

ok heap reached 0 count in less than 50 steps

Test #7:

score: 0
Accepted
time: 2ms
memory: 3320kb

input:

4418 -527

output:

6
1 8
2 3
1 -3
2 2
1 4
2 -9

result:

ok heap reached 0 count in less than 50 steps

Test #8:

score: 0
Accepted
time: 2ms
memory: 3420kb

input:

55796 83094

output:

6
2 -1
1 -2
2 -23
1 4
2 -38
1 4

result:

ok heap reached 0 count in less than 50 steps

Test #9:

score: 0
Accepted
time: 3ms
memory: 3340kb

input:

581706 382159

output:

10
1 -2
2 2
1 11
2 -5
1 3
2 -2
1 -3
2 -7
1 4
2 7

result:

ok heap reached 0 count in less than 50 steps

Test #10:

score: 0
Accepted
time: 2ms
memory: 3376kb

input:

-1570717 -5452307

output:

12
2 -3
1 -2
2 -8
1 -5
2 -3
1 10
2 2
1 3
2 -3
1 5
2 -2
1 -3

result:

ok heap reached 0 count in less than 50 steps

Test #11:

score: 0
Accepted
time: 2ms
memory: 3376kb

input:

35296299 62120456

output:

10
2 -2
1 4
2 6
1 55
2 -3
1 11
2 5
1 3
2 -10
1 -5

result:

ok heap reached 0 count in less than 50 steps

Test #12:

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

input:

133453354 276321715

output:

12
2 -2
1 -14
2 -6
1 4
2 -3
1 -3
2 -3
1 3
2 -20
1 5
2 7
1 7

result:

ok heap reached 0 count in less than 50 steps

Test #13:

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

input:

4087302427 739712346

output:

15
1 -6
2 2
1 9
2 3
1 2
2 3
1 -2
2 -5
1 6
2 3
1 -2
2 -15
1 23
2 -4
1 4

result:

ok heap reached 0 count in less than 50 steps

Test #14:

score: 0
Accepted
time: 2ms
memory: 3340kb

input:

30857859855 -36651946276

output:

14
2 1
1 5
2 3
1 14
2 3
1 8
2 33
1 7
2 3
1 -5
2 15
1 -2
2 -2
1 -21

result:

ok heap reached 0 count in less than 50 steps

Test #15:

score: 0
Accepted
time: 2ms
memory: 3312kb

input:

290684430189 -337396975722

output:

17
2 1
1 6
2 4
1 2
2 20
1 -4
2 3
1 -7
2 3
1 -2
2 -10
1 -3
2 -3
1 -3
2 -3
1 2
2 4

result:

ok heap reached 0 count in less than 50 steps

Test #16:

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

input:

4018564636210 2812471427308

output:

17
1 -1
2 -2
1 -3
2 -76
1 -2
2 -3
1 2
2 50
1 -3
2 2
1 3
2 -9
1 4
2 4
1 -5
2 117
1 3

result:

ok heap reached 0 count in less than 50 steps

Test #17:

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

input:

46017810015419 -48982225298334

output:

22
2 1
1 16
2 -2
1 -10
2 -5
1 -2
2 -7
1 -2
2 -3
1 -2
2 -3
1 -7
2 -3
1 8
2 4
1 -4
2 -8
1 2
2 5
1 -4
2 16
1 2

result:

ok heap reached 0 count in less than 50 steps

Test #18:

score: 0
Accepted
time: 2ms
memory: 3316kb

input:

-791828028554116 -417054265497197

output:

18
1 -2
2 10
1 -7
2 -3
1 6
2 4
1 4
2 -11
1 107
2 -28
1 8
2 5
1 -43
2 -3
1 -5
2 4
1 2
2 2

result:

ok heap reached 0 count in less than 50 steps

Test #19:

score: 0
Accepted
time: 2ms
memory: 3316kb

input:

9958409834380717 -5355316404922545

output:

22
1 2
2 -7
1 -8
2 -3
1 3
2 -3
1 -14
2 12
1 -2
2 -16
1 11
2 -11
1 4
2 4
1 -4
2 5
1 -2
2 -13
1 33
2 -6
1 2
2 2

result:

ok heap reached 0 count in less than 50 steps

Test #20:

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

input:

73118300939404300 -89660288210986608

output:

23
2 1
1 4
2 2
1 3
2 -3
1 3
2 2
1 18
2 8
1 -3
2 2
1 4
2 23
1 -4
2 48
1 7
2 -62
1 6
2 -3
1 -5
2 -3
1 4
2 5

result:

ok heap reached 0 count in less than 50 steps

Test #21:

score: 0
Accepted
time: 2ms
memory: 3376kb

input:

-698819961200024568 438960282374739748

output:

29
1 2
2 -2
1 -2
2 -5
1 2
2 2
1 5
2 2
1 5
2 -2
1 -3
2 -3
1 -2
2 -11
1 -3
2 4
1 2
2 4
1 2
2 24
1 5
2 -3
1 -2
2 -7
1 5
2 -6
1 12
2 6
1 -8

result:

ok heap reached 0 count in less than 50 steps

Test #22:

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

input:

1 3

output:

1
2 -3

result:

ok heap reached 0 count in less than 50 steps

Test #23:

score: 0
Accepted
time: 2ms
memory: 3364kb

input:

-89 144

output:

6
2 2
1 -3
2 3
1 -3
2 2
1 2

result:

ok heap reached 0 count in less than 50 steps

Test #24:

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

input:

10946 -17711

output:

11
2 2
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -2
2 -2

result:

ok heap reached 0 count in less than 50 steps

Test #25:

score: 0
Accepted
time: 2ms
memory: 3340kb

input:

2178309 1346269

output:

16
1 -2
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -2
2 -2

result:

ok heap reached 0 count in less than 50 steps

Test #26:

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

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

input:

365435296162 225851433717

output:

28
1 -2
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3

result:

ok heap reached 0 count in less than 50 steps

Test #28:

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

input:

225851433717 -679891637638612258

output:

4
2 3010349
1 3010349
2 -9378
1 -8

result:

ok heap reached 0 count in less than 50 steps

Test #29:

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

input:

23416728348467685 14472334024676221

output:

40
1 -2
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -2
2 -2

result:

ok heap reached 0 count in less than 50 steps

Test #30:

score: 0
Accepted
time: 2ms
memory: 3312kb

input:

-23416728348467685 -37889062373143906

output:

40
2 -2
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3

result:

ok heap reached 0 count in less than 50 steps

Test #31:

score: 0
Accepted
time: 2ms
memory: 3456kb

input:

160500643816367088 -420196140727489673

output:

42
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3

result:

ok heap reached 0 count in less than 50 steps

Test #32:

score: 0
Accepted
time: 2ms
memory: 3440kb

input:

-679891637638612258 420196140727489673

output:

43
1 2
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3

result:

ok heap reached 0 count in less than 50 steps

Test #33:

score: 0
Accepted
time: 2ms
memory: 3372kb

input:

420196140727489673 679891637638612258

output:

43
2 -2
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3

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: 2ms
memory: 3372kb

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

input:

225851433717 591286729879

output:

28
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3

result:

ok heap reached 0 count in less than 50 steps

Test #37:

score: 0
Accepted
time: 2ms
memory: 3376kb

input:

14472334024676221 8944394323791464

output:

39
1 -2
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3

result:

ok heap reached 0 count in less than 50 steps

Test #38:

score: 0
Accepted
time: 2ms
memory: 3332kb

input:

-1000000000000000000 1000000000000000000

output:

1
1 1

result:

ok heap reached 0 count in less than 50 steps

Test #39:

score: 0
Accepted
time: 2ms
memory: 3452kb

input:

-679891637638612256 420196140727489673

output:

34
1 2
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 3
2 -3
1 2
2 3
1 -2
2 -6
1 7
2 -7
1 7
2 -7
1 7
2 -7
1 7
2 -7
1 6
2 2

result:

ok heap reached 0 count in less than 50 steps

Test #40:

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

input:

-5527939700884765 14472334024676228

output:

30
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -3
2 3
1 -2
2 -4
1 3
2 6
1 -30
2 -3
1 11
2 3
1 4
2 -6
1 -4
2 4
1 6

result:

ok heap reached 0 count in less than 50 steps