QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #301504 | #2731. Cartesian Conquest | Camillus | 13 | 467ms | 1792464kb | C++20 | 1.8kb | 2024-01-09 23:51:08 | 2024-01-09 23:51:09 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
struct pair_hash {
size_t operator()(const pair<int, int> &p) const {
return p.first ^ p.second;
}
};
unordered_map<pair<int, int>, int, pair_hash> saved_mx;
int mx_func(int n, int m) {
if (n > m) {
swap(n, m);
}
if (saved_mx.contains(make_pair(n, m))) {
return saved_mx[make_pair(n, m)];
}
int cur = 0;
if (n % 2 == 0 && m - n / 2 > 0) {
cur = max(cur, mx_func(n, m - n / 2));
}
if (m % 2 == 0 && n - m / 2 > 0) {
cur = max(cur, mx_func(n - m / 2, m));
}
if (m - 2 * n > 0) {
cur = max(cur, mx_func(n, m - 2 * n));
}
if (n - 2 * m > 0) {
cur = max(cur, mx_func(n - 2 * m, m));
}
return saved_mx[make_pair(n, m)] = cur + 1;
}
unordered_map<pair<int, int>, int, pair_hash> saved_mn;
int mn_func(int n, int m) {
if (n > m) {
swap(n, m);
}
if (saved_mn.contains(make_pair(n, m))) {
return saved_mn[make_pair(n, m)];
}
if (n == 2 * m || m == 2 * n) {
return 1;
}
int cur = INT32_MAX;
if (n % 2 == 0 && m - n / 2 > 0) {
cur = min(cur, mn_func(n, m - n / 2));
}
if (m % 2 == 0 && n - m / 2 > 0) {
cur = min(cur, mn_func(n - m / 2, m));
}
if (m - 2 * n > 0) {
cur = min(cur, mn_func(n, m - 2 * n));
}
if (n - 2 * m > 0) {
cur = min(cur, mn_func(n - 2 * m, m));
}
return saved_mn[make_pair(n, m)] = cur + 1;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
saved_mn.reserve(1e8);
saved_mx.reserve(1e8);
int n, m;
cin >> n >> m;
cout << mn_func(n, m) << ' ' << mx_func(n, m) << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 199ms
memory: 1588624kb
input:
2 1
output:
1 1
result:
ok single line: '1 1'
Test #2:
score: 0
Accepted
time: 238ms
memory: 1588560kb
input:
2 4
output:
1 4
result:
ok single line: '1 4'
Test #3:
score: 0
Accepted
time: 200ms
memory: 1588564kb
input:
5 4
output:
4 4
result:
ok single line: '4 4'
Test #4:
score: 0
Accepted
time: 200ms
memory: 1588568kb
input:
4 6
output:
3 6
result:
ok single line: '3 6'
Test #5:
score: 0
Accepted
time: 251ms
memory: 1588944kb
input:
1000 2
output:
250 1000
result:
ok single line: '250 1000'
Test #6:
score: 0
Accepted
time: 192ms
memory: 1588608kb
input:
1 1000
output:
500 500
result:
ok single line: '500 500'
Test #7:
score: 0
Accepted
time: 195ms
memory: 1588572kb
input:
1000 1000
output:
2 8
result:
ok single line: '2 8'
Test #8:
score: 0
Accepted
time: 200ms
memory: 1588612kb
input:
872 976
output:
11 133
result:
ok single line: '11 133'
Test #9:
score: 0
Accepted
time: 205ms
memory: 1588536kb
input:
768 992
output:
8 124
result:
ok single line: '8 124'
Test #10:
score: 0
Accepted
time: 207ms
memory: 1588508kb
input:
960 896
output:
6 85
result:
ok single line: '6 85'
Test #11:
score: 0
Accepted
time: 187ms
memory: 1588540kb
input:
832 992
output:
6 182
result:
ok single line: '6 182'
Test #12:
score: 0
Accepted
time: 199ms
memory: 1588560kb
input:
26 7
output:
8 8
result:
ok single line: '8 8'
Test #13:
score: 0
Accepted
time: 200ms
memory: 1588612kb
input:
38 71
output:
7 30
result:
ok single line: '7 30'
Test #14:
score: 0
Accepted
time: 191ms
memory: 1588544kb
input:
52 22
output:
5 17
result:
ok single line: '5 17'
Test #15:
score: 0
Accepted
time: 193ms
memory: 1588532kb
input:
18 74
output:
6 26
result:
ok single line: '6 26'
Test #16:
score: 0
Accepted
time: 191ms
memory: 1588592kb
input:
63 88
output:
12 12
result:
ok single line: '12 12'
Test #17:
score: 0
Accepted
time: 164ms
memory: 1588600kb
input:
378 251
output:
11 43
result:
ok single line: '11 43'
Test #18:
score: 0
Accepted
time: 191ms
memory: 1588612kb
input:
981 122
output:
12 52
result:
ok single line: '12 52'
Test #19:
score: 0
Accepted
time: 188ms
memory: 1588596kb
input:
410 478
output:
10 82
result:
ok single line: '10 82'
Subtask #2:
score: 8
Accepted
Test #20:
score: 8
Accepted
time: 200ms
memory: 1588912kb
input:
2 1001
output:
251 1001
result:
ok single line: '251 1001'
Test #21:
score: 0
Accepted
time: 236ms
memory: 1666812kb
input:
1 1000000
output:
500000 500000
result:
ok single line: '500000 500000'
Test #22:
score: 0
Accepted
time: 199ms
memory: 1588572kb
input:
1000000 1000000
output:
2 25
result:
ok single line: '2 25'
Test #23:
score: 0
Accepted
time: 176ms
memory: 1589180kb
input:
80400 64364
output:
18 622
result:
ok single line: '18 622'
Test #24:
score: 0
Accepted
time: 219ms
memory: 1588988kb
input:
5290 4513
output:
15 633
result:
ok single line: '15 633'
Test #25:
score: 0
Accepted
time: 217ms
memory: 1588604kb
input:
663518 314601
output:
82 148
result:
ok single line: '82 148'
Test #26:
score: 0
Accepted
time: 401ms
memory: 1792464kb
input:
913836 913838
output:
34 913838
result:
ok single line: '34 913838'
Test #27:
score: 0
Accepted
time: 347ms
memory: 1745240kb
input:
995579 995578
output:
506 497793
result:
ok single line: '506 497793'
Test #28:
score: 0
Accepted
time: 344ms
memory: 1746744kb
input:
997467 997466
output:
36 498737
result:
ok single line: '36 498737'
Test #29:
score: 0
Accepted
time: 245ms
memory: 1668356kb
input:
769244 961556
output:
33 384627
result:
ok single line: '33 384627'
Test #30:
score: 0
Accepted
time: 292ms
memory: 1597388kb
input:
884224 753344
output:
18 9147
result:
ok single line: '18 9147'
Test #31:
score: 0
Accepted
time: 244ms
memory: 1595792kb
input:
893056 501504
output:
16 4043
result:
ok single line: '16 4043'
Test #32:
score: 0
Accepted
time: 389ms
memory: 1601584kb
input:
892928 841728
output:
9 3246
result:
ok single line: '9 3246'
Test #33:
score: 0
Accepted
time: 375ms
memory: 1600312kb
input:
774144 980992
output:
11 3246
result:
ok single line: '11 3246'
Test #34:
score: 0
Accepted
time: 352ms
memory: 1599760kb
input:
741376 956416
output:
12 3242
result:
ok single line: '12 3242'
Test #35:
score: 0
Accepted
time: 407ms
memory: 1602716kb
input:
971776 790528
output:
15 3910
result:
ok single line: '15 3910'
Test #36:
score: 0
Accepted
time: 320ms
memory: 1600348kb
input:
740096 972288
output:
16 4660
result:
ok single line: '16 4660'
Test #37:
score: 0
Accepted
time: 424ms
memory: 1601572kb
input:
996352 771072
output:
12 7065
result:
ok single line: '12 7065'
Test #38:
score: 0
Accepted
time: 380ms
memory: 1602136kb
input:
875520 929792
output:
13 5672
result:
ok single line: '13 5672'
Test #39:
score: 0
Accepted
time: 467ms
memory: 1602672kb
input:
982016 915456
output:
16 4521
result:
ok single line: '16 4521'
Test #40:
score: 0
Accepted
time: 199ms
memory: 1588616kb
input:
949669 211072
output:
184 722
result:
ok single line: '184 722'
Test #41:
score: 0
Accepted
time: 180ms
memory: 1589208kb
input:
139034 355934
output:
21 363
result:
ok single line: '21 363'
Test #42:
score: 0
Accepted
time: 192ms
memory: 1588580kb
input:
576184 726923
output:
30 217
result:
ok single line: '30 217'
Test #43:
score: 0
Accepted
time: 203ms
memory: 1588572kb
input:
348991 632952
output:
38 223
result:
ok single line: '38 223'
Test #44:
score: 0
Accepted
time: 211ms
memory: 1588592kb
input:
465119 181796
output:
26 110
result:
ok single line: '26 110'
Subtask #3:
score: 0
Memory Limit Exceeded
Test #45:
score: 0
Memory Limit Exceeded
input:
100000000 2