QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#301502#2731. Cartesian ConquestCamillus13 1553ms270696kbC++201.6kb2024-01-09 23:44:302024-01-09 23:44:30

Judging History

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

  • [2024-01-09 23:44:30]
  • 评测
  • 测评结果：13
  • 用时：1553ms
  • 内存：270696kb
查看
  • [2024-01-09 23:44:30]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;

map<pair<int, int>, int> 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;
}

map<pair<int, int>, int> 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);
    
    int n, m;
    cin >> n >> m;

    cout << mn_func(n, m) << ' ' << mx_func(n, m) << '\n';
    return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 0ms
memory: 3668kb

input:

2 1

output:

1 1

result:

ok single line: '1 1'

Test #2:

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

input:

2 4

output:

1 4

result:

ok single line: '1 4'

Test #3:

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

input:

5 4

output:

4 4

result:

ok single line: '4 4'

Test #4:

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

input:

4 6

output:

3 6

result:

ok single line: '3 6'

Test #5:

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

input:

1000 2

output:

250 1000

result:

ok single line: '250 1000'

Test #6:

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

input:

1 1000

output:

500 500

result:

ok single line: '500 500'

Test #7:

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

input:

1000 1000

output:

2 8

result:

ok single line: '2 8'

Test #8:

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

input:

872 976

output:

11 133

result:

ok single line: '11 133'

Test #9:

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

input:

768 992

output:

8 124

result:

ok single line: '8 124'

Test #10:

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

input:

960 896

output:

6 85

result:

ok single line: '6 85'

Test #11:

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

input:

832 992

output:

6 182

result:

ok single line: '6 182'

Test #12:

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

input:

26 7

output:

8 8

result:

ok single line: '8 8'

Test #13:

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

input:

38 71

output:

7 30

result:

ok single line: '7 30'

Test #14:

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

input:

52 22

output:

5 17

result:

ok single line: '5 17'

Test #15:

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

input:

18 74

output:

6 26

result:

ok single line: '6 26'

Test #16:

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

input:

63 88

output:

12 12

result:

ok single line: '12 12'

Test #17:

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

input:

378 251

output:

11 43

result:

ok single line: '11 43'

Test #18:

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

input:

981 122

output:

12 52

result:

ok single line: '12 52'

Test #19:

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

input:

410 478

output:

10 82

result:

ok single line: '10 82'

Subtask #2:

score: 8
Accepted

Test #20:

score: 8
Accepted
time: 1ms
memory: 3820kb

input:

2 1001

output:

251 1001

result:

ok single line: '251 1001'

Test #21:

score: 0
Accepted
time: 203ms
memory: 105112kb

input:

1 1000000

output:

500000 500000

result:

ok single line: '500000 500000'

Test #22:

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

input:

1000000 1000000

output:

2 25

result:

ok single line: '2 25'

Test #23:

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

input:

80400 64364

output:

18 622

result:

ok single line: '18 622'

Test #24:

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

input:

5290 4513

output:

15 633

result:

ok single line: '15 633'

Test #25:

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

input:

663518 314601

output:

82 148

result:

ok single line: '82 148'

Test #26:

score: 0
Accepted
time: 1553ms
memory: 270696kb

input:

913836 913838

output:

34 913838

result:

ok single line: '34 913838'

Test #27:

score: 0
Accepted
time: 993ms
memory: 209664kb

input:

995579 995578

output:

506 497793

result:

ok single line: '506 497793'

Test #28:

score: 0
Accepted
time: 1122ms
memory: 211680kb

input:

997467 997466

output:

36 498737

result:

ok single line: '36 498737'

Test #29:

score: 0
Accepted
time: 572ms
memory: 107852kb

input:

769244 961556

output:

33 384627

result:

ok single line: '33 384627'

Test #30:

score: 0
Accepted
time: 62ms
memory: 15260kb

input:

884224 753344

output:

18 9147

result:

ok single line: '18 9147'

Test #31:

score: 0
Accepted
time: 61ms
memory: 12988kb

input:

893056 501504

output:

16 4043

result:

ok single line: '16 4043'

Test #32:

score: 0
Accepted
time: 124ms
memory: 20700kb

input:

892928 841728

output:

9 3246

result:

ok single line: '9 3246'

Test #33:

score: 0
Accepted
time: 114ms
memory: 18948kb

input:

774144 980992

output:

11 3246

result:

ok single line: '11 3246'

Test #34:

score: 0
Accepted
time: 110ms
memory: 18440kb

input:

741376 956416

output:

12 3242

result:

ok single line: '12 3242'

Test #35:

score: 0
Accepted
time: 127ms
memory: 22156kb

input:

971776 790528

output:

15 3910

result:

ok single line: '15 3910'

Test #36:

score: 0
Accepted
time: 105ms
memory: 19032kb

input:

740096 972288

output:

16 4660

result:

ok single line: '16 4660'

Test #37:

score: 0
Accepted
time: 123ms
memory: 20856kb

input:

996352 771072

output:

12 7065

result:

ok single line: '12 7065'

Test #38:

score: 0
Accepted
time: 118ms
memory: 21332kb

input:

875520 929792

output:

13 5672

result:

ok single line: '13 5672'

Test #39:

score: 0
Accepted
time: 145ms
memory: 22416kb

input:

982016 915456

output:

16 4521

result:

ok single line: '16 4521'

Test #40:

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

input:

949669 211072

output:

184 722

result:

ok single line: '184 722'

Test #41:

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

input:

139034 355934

output:

21 363

result:

ok single line: '21 363'

Test #42:

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

input:

576184 726923

output:

30 217

result:

ok single line: '30 217'

Test #43:

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

input:

348991 632952

output:

38 223

result:

ok single line: '38 223'

Test #44:

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

input:

465119 181796

output:

26 110

result:

ok single line: '26 110'

Subtask #3:

score: 0
Runtime Error

Test #45:

score: 0
Runtime Error

input:

100000000 2

output:

result:
English 繁體中文 简体中文

Server Time: 2024-11-30 02:42:14 | OpenSource Project