QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#301504#2731. Cartesian ConquestCamillus13 467ms1792464kbC++201.8kb2024-01-09 23:51:082024-01-09 23:51:09

Judging History

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

  • [2024-01-09 23:51:09]
  • 评测
  • 测评结果：13
  • 用时：467ms
  • 内存：1792464kb
查看
  • [2024-01-09 23:51:08]
  • 提交

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;
}
源文件, 语言: C++20

详细

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

output:

result:
English 繁體中文 简体中文

服务器时间: 2024-11-30 02:26:40 | 开源项目