QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#86516 | #1900. Octopus Game | triplem5ds# | AC ✓ | 3ms | 3552kb | C++20 | 2.2kb | 2023-03-09 23:43:10 | 2023-03-09 23:43:12 |
Judging History
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 (abs(a) < abs(b))swap(a, b), swapped ^= 1;
if (!b)return;
else {
int k = a / b;
int val1 = abs(a - k * b);
int val2 = abs(a - (k + 1) * b);
int val3 = abs(a - (k - 1) * b);
if (val1 == min({val1, val2, val3})) {
if (k)ans.push_back({swapped + 1, -k});
solve(b, a - k * b, swapped ^ 1);
} else if (val2 == min({val1, val2, val3})) {
if (k + 1)ans.push_back({swapped + 1, -k - 1});
solve(b, a - (k + 1) * b, swapped ^ 1);
} else {
if (k - 1)ans.push_back({swapped + 1, -k + 1});
solve(b, a - (k - 1) * b, swapped ^ 1);
}
}
}
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;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3516kb
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: 3348kb
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: 1ms
memory: 3360kb
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: 2ms
memory: 3360kb
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: 3540kb
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: 3360kb
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: 1ms
memory: 3392kb
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: 3548kb
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: 2ms
memory: 3368kb
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: 0ms
memory: 3360kb
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: 0ms
memory: 3548kb
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: 1ms
memory: 3408kb
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: 2ms
memory: 3372kb
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: 0ms
memory: 3364kb
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: 0ms
memory: 3408kb
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: 2ms
memory: 3520kb
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: 1ms
memory: 3396kb
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: 0ms
memory: 3304kb
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: 3364kb
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: 3320kb
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: 3520kb
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: 2ms
memory: 3348kb
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: 3376kb
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: 2ms
memory: 3548kb
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: 3300kb
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: 2ms
memory: 3324kb
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: 2ms
memory: 3392kb
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: 1ms
memory: 3352kb
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: 2ms
memory: 3516kb
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: 3360kb
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: 3320kb
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: 0ms
memory: 3540kb
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: 3368kb
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: 3ms
memory: 3404kb
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: 3300kb
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: 3384kb
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: 0ms
memory: 3484kb
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: 3344kb
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: 3552kb
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: 0ms
memory: 3548kb
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