QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#86509#1900. Octopus Gametriplem5ds#WA 2ms3544kbC++201.8kb2023-03-09 23:15:532023-03-09 23:15: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-09 23:15:56]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3544kb
  • [2023-03-09 23:15:53]
  • 提交

answer

///Enta etfsh5t nseet el rank

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

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>;
#define pb push_back
#define F first
#define S second
#define f(i, a, b) for (int i = a; i < b; i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(x) (int)(x).size()
//#define mp(x, y) make_pair(x, y)
#define popCnt(x) (__builtin_popcountll(x))
#define int ll

using ll = long long;
using ull = unsigned long long;
using uint = uint32_t;
using ii = pair<int, int>;

const int N = 3e6 + 6, A = 26, LG = 18, MOD = (119 << 23) + 1;
const long double PI = acos(-1);
const long double EPS = 1e-9;
const ll INF = 1e15;
vector<ii> ans;

void solve(int a, int b, int swapped) {
    if (!b)return;
    else {
        int k = a / b;
        if (abs(b - (a - k * b)) < abs(b - (a - (k + 1) * b))) {
            ans.push_back({swapped + 1, -k});
            solve(b, a % b, swapped ^ 1);
        } else {
            ans.push_back({swapped + 1, -k - 1});
            solve(b, a - (k + 1) * b, swapped);
        }
    }
}

void doWork() {

    int a, b;
    cin >> a >> b;
    solve(a, b, 0);
    cout << ans.size() << '\n';
    for (auto p: ans)
        cout << p.F << ' ' << p.S << '\n';

}


int32_t main() {
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif // ONLINE_JUDGE
    int t = 1;
//    cin >> t;
    while (t--)
        doWork();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

-3 9

output:

2
1 0
2 3

result:

ok heap reached 0 count in less than 50 steps

Test #2:

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

input:

-27 57

output:

3
1 0
2 2
1 9

result:

ok heap reached 0 count in less than 50 steps

Test #3:

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

input:

56 15

output:

5
1 -3
2 -1
1 -2
2 -1
1 -3

result:

ok heap reached 0 count in less than 50 steps

Test #4:

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

input:

6 -2

output:

1
1 3

result:

ok heap reached 0 count in less than 50 steps

Test #5:

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

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

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

input:

4418 -527

output:

9
1 8
2 2
1 1
2 1
1 1
2 1
1 3
2 1
1 8

result:

ok heap reached 0 count in less than 50 steps

Test #8:

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

input:

55796 83094

output:

10
1 0
2 -1
1 -2
2 -22
1 -1
2 -2
1 -1
2 -36
1 -1
2 -3

result:

ok heap reached 0 count in less than 50 steps

Test #9:

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

input:

581706 382159

output:

15
1 -1
2 -1
1 -1
2 -10
1 -1
2 -3
1 -1
2 -1
1 -1
2 -1
1 -3
2 -6
1 -1
2 -3
1 -7

result:

ok heap reached 0 count in less than 50 steps

Test #10:

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

input:

-1570717 -5452307

output:

17
1 0
2 -3
1 -2
2 -8
1 -5
2 -2
1 -1
2 -9
1 -2
2 -2
1 -1
2 -1
1 -1
2 -3
1 -1
2 -1
1 -3

result:

ok heap reached 0 count in less than 50 steps

Test #11:

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

input:

35296299 62120456

output:

15
1 0
2 -1
1 -1
2 -3
1 -6
2 -54
1 -1
2 -1
1 -1
2 -10
1 -5
2 -2
1 -1
2 -9
1 -5

result:

ok heap reached 0 count in less than 50 steps

Test #12:

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

input:

133453354 276321715

output:

18
1 0
2 -2
1 -14
2 -5
1 -1
2 -2
1 -1
2 -2
1 -3
2 -2
1 -1
2 -1
1 -1
2 -18
1 -1
2 -4
1 -7
2 -7

result:

ok heap reached 0 count in less than 50 steps

Test #13:

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

input:

4087302427 739712346

output:

22
1 -5
2 -1
1 -1
2 -9
1 -3
2 -2
1 -2
2 -1
1 -1
2 -4
1 -1
2 -5
1 -2
2 -1
1 -1
2 -14
1 -1
2 -21
1 -1
2 -2
1 -1
2 -3

result:

ok heap reached 0 count in less than 50 steps

Test #14:

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

input:

30857859855 -36651946276

output:

18
1 0
2 1
1 5
2 3
1 14
2 3
1 8
2 33
1 7
2 2
1 1
2 3
1 1
2 13
1 1
2 1
1 2
2 21

result:

ok heap reached 0 count in less than 50 steps

Test #15:

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

input:

290684430189 -337396975722

output:

24
1 0
2 1
1 6
2 4
1 2
2 19
1 1
2 2
1 1
2 1
1 1
2 5
1 1
2 1
1 1
2 1
1 10
2 3
1 3
2 3
1 2
2 1
1 1
2 4

result:

ok heap reached 0 count in less than 50 steps

Test #16:

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

input:

4018564636210 2812471427308

output:

24
1 -1
2 -2
1 -3
2 -76
1 -2
2 -2
1 -1
2 -1
1 -49
2 -1
1 -1
2 -1
1 -1
2 -2
1 -1
2 -7
1 -1
2 -3
1 -3
2 -1
1 -3
2 -1
1 -116
2 -3

result:

ok heap reached 0 count in less than 50 steps

Test #17:

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

input:

46017810015419 -48982225298334

output:

29
1 0
2 1
1 15
2 1
1 1
2 10
1 5
2 2
1 7
2 2
1 3
2 2
1 3
2 7
1 2
2 1
1 7
2 3
1 1
2 3
1 7
2 1
1 1
2 4
1 1
2 2
1 1
2 15
1 2

result:

ok heap reached 0 count in less than 50 steps

Test #18:

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

input:

-791828028554116 -417054265497197

output:

27
1 -1
2 -1
1 -8
2 -1
1 -6
2 -2
1 -1
2 -5
1 -4
2 -3
1 -1
2 -9
1 -1
2 -105
1 -1
2 -26
1 -1
2 -7
1 -4
2 -1
1 -42
2 -3
1 -4
2 -1
1 -3
2 -2
1 -2

result:

ok heap reached 0 count in less than 50 steps

Test #19:

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

input:

9958409834380717 -5355316404922545

output:

36
1 1
2 1
1 6
2 8
1 2
2 1
1 1
2 1
1 2
2 13
1 1
2 10
1 1
2 1
1 15
2 1
1 9
2 1
1 9
2 1
1 3
2 3
1 1
2 2
1 1
2 3
1 1
2 1
1 12
2 1
1 31
2 1
1 4
2 1
1 1
2 2

result:

ok heap reached 0 count in less than 50 steps

Test #20:

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

input:

73118300939404300 -89660288210986608

output:

34
1 0
2 1
1 4
2 2
1 2
2 1
1 1
2 1
1 2
2 2
1 18
2 7
1 1
2 1
1 1
2 1
1 4
2 22
1 1
2 2
1 1
2 47
1 6
2 1
1 60
2 1
1 4
2 1
1 2
2 5
1 2
2 1
1 3
2 5

result:

ok heap reached 0 count in less than 50 steps

Test #21:

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

input:

-698819961200024568 438960282374739748

output:

38
1 1
2 1
1 1
2 2
1 4
2 1
1 1
2 2
1 5
2 2
1 4
2 1
1 1
2 3
1 3
2 2
1 11
2 2
1 1
2 3
1 2
2 4
1 2
2 24
1 4
2 1
1 2
2 2
1 6
2 1
1 3
2 1
1 4
2 1
1 11
2 5
1 1
2 7

result:

ok heap reached 0 count in less than 50 steps

Test #22:

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

input:

1 3

output:

2
1 0
2 -3

result:

ok heap reached 0 count in less than 50 steps

Test #23:

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

input:

-89 144

output:

11
1 0
2 1
1 1
2 1
1 1
2 1
1 1
2 1
1 1
2 1
1 2

result:

ok heap reached 0 count in less than 50 steps

Test #24:

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

input:

10946 -17711

output:

21
1 0
2 1
1 1
2 1
1 1
2 1
1 1
2 1
1 1
2 1
1 1
2 1
1 1
2 1
1 1
2 1
1 1
2 1
1 1
2 1
1 2

result:

ok heap reached 0 count in less than 50 steps

Test #25:

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

input:

2178309 1346269

output:

30
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -2

result:

ok heap reached 0 count in less than 50 steps

Test #26:

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

input:

-1346269 679891637638612258

output:

12
1 0
2 505019158606
1 1
2 16
1 1
2 16
1 1
2 16
1 1
2 16
1 1
2 12

result:

ok heap reached 0 count in less than 50 steps

Test #27:

score: -100
Wrong Answer
time: 0ms
memory: 3372kb

input:

365435296162 225851433717

output:

55
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -1
2 -1
1 -2

result:

wrong answer used more than 50 steps