QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#376849#2160. Cardiologywillow#AC ✓12ms11756kbC++171.7kb2024-04-04 17:37:442024-04-04 17:37:45

Judging History

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

  • [2024-04-04 17:37:45]
  • 评测
  • 测评结果:AC
  • 用时:12ms
  • 内存:11756kb
  • [2024-04-04 17:37:44]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int R, C, ansp, ansd, dep[maxn], vis[maxn];
vector<pair<int, int> > cen;
int Solve(int r, int tar) {
// cerr << "Solve(" << r << ", " << tar << ")" << endl;
    if(r == tar)
        return dep[r] = 1;
    if(dep[r])
        return dep[r];
    assert(vis[r] == 0);
    vis[r] = 1;
    long long nxt = 1ll * (ansp - 1) * R + r;
// cerr << r << " " << nxt << " " << (nxt - 1) / C + 1 << endl;
    return dep[r] = Solve((nxt - 1) / C + 1, tar) + 1;
}
int main() {
    scanf("%d%d", &R, &C);
    for(int i = (R + 1) / 2; i <= (R + 2) / 2; ++ i) {
        for(int j = (C + 1) / 2; j <= (C + 2) / 2; ++ j) {
            cen.push_back({i, j});
        }
    }
    ansd = R + C + 1;
    for(int i = 1; i <= C; ++ i) {
        long long tmp = 1ll * (i - 1) * R + C;
        int rem = tmp % (C - 1), tar = tmp / (C - 1);
// cerr << tmp << "? " << rem << " " << tar << endl;
        if(rem == 1 && tar > 1)
            continue;
        if(rem == 0)
            rem += C - 1, -- tar;
        // Center is (tar, rem);
        int d = R + C + 1;
        for(auto [x, y] : cen)
            d = min(d, abs(x - tar) + abs(y - rem));
// cerr << i << ": Cen(" << tar << ", " << rem << ") d = " << d << endl;
        if(d < ansd)
            ansd = d, ansp = i;
    }
    long long tmp = 1ll * (ansp - 1) * R + C;
    int rem = tmp % (C - 1), tar = tmp / (C - 1);
    if(rem == 0)
        rem += C - 1, -- tar;
// cerr << "Ansp = " << ansp << " " << rem << " " << tar << endl;
// return 0;
    int mx = 0;
    for(int i = 1; i <= R; ++ i) {
        mx = max(mx, Solve(i, tar));
    }
    printf("%d %d %d %d\n", ansp, tar, rem, mx);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 3924kb

input:

6666 966364

output:

473832 3269 483163 2

result:

ok single line: '473832 3269 483163 2'

Test #2:

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

input:

36 906986

output:

12598 1 453493 2

result:

ok single line: '12598 1 453493 2'

Test #3:

score: 0
Accepted
time: 6ms
memory: 9320kb

input:

704877 297616

output:

148803 352426 140980 3

result:

ok single line: '148803 352426 140980 3'

Test #4:

score: 0
Accepted
time: 10ms
memory: 11624kb

input:

1000000 1000000

output:

500000 500000 500000 2

result:

ok single line: '500000 500000 500000 2'

Test #5:

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

input:

2 2

output:

1 1 1 2

result:

ok single line: '1 1 1 2'

Test #6:

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

input:

1000000 2

output:

1 1 1 21

result:

ok single line: '1 1 1 21'

Test #7:

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

input:

2 1000000

output:

250001 1 500001 2

result:

ok single line: '250001 1 500001 2'

Test #8:

score: 0
Accepted
time: 7ms
memory: 11576kb

input:

985391 511611

output:

255806 492696 255806 3

result:

ok single line: '255806 492696 255806 3'

Test #9:

score: 0
Accepted
time: 6ms
memory: 8200kb

input:

435766 614914

output:

304739 215957 307481 2

result:

ok single line: '304739 215957 307481 2'

Test #10:

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

input:

818196 58

output:

29 401921 49 5

result:

ok single line: '29 401921 49 5'

Test #11:

score: 0
Accepted
time: 4ms
memory: 6940kb

input:

401765 19

output:

10 200883 10 6

result:

ok single line: '10 200883 10 6'

Test #12:

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

input:

95 912669

output:

456335 48 456335 2

result:

ok single line: '456335 48 456335 2'

Test #13:

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

input:

81 429950

output:

2655 1 214975 2

result:

ok single line: '2655 1 214975 2'

Test #14:

score: 0
Accepted
time: 12ms
memory: 11676kb

input:

999956 999959

output:

249991 249990 499979 3

result:

ok single line: '249991 249990 499979 3'

Test #15:

score: 0
Accepted
time: 8ms
memory: 11752kb

input:

999935 999946

output:

449976 449971 499976 3

result:

ok single line: '449976 449971 499976 3'

Test #16:

score: 0
Accepted
time: 6ms
memory: 11756kb

input:

999951 999952

output:

1 1 1 2

result:

ok single line: '1 1 1 2'

Test #17:

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

input:

106352 224337

output:

112111 53149 112993 2

result:

ok single line: '112111 53149 112993 2'

Test #18:

score: 0
Accepted
time: 7ms
memory: 8896kb

input:

651870 786333

output:

392936 325744 393775 2

result:

ok single line: '392936 325744 393775 2'

Test #19:

score: 0
Accepted
time: 9ms
memory: 10512kb

input:

838522 972888

output:

486249 419093 486853 2

result:

ok single line: '486249 419093 486853 2'