QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#59620#2160. CardiologylosPatrons#AC ✓63ms3776kbC++143.6kb2022-10-31 04:04:072022-10-31 04:04:08

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-31 04:04:08]
  • 评测
  • 测评结果:AC
  • 用时:63ms
  • 内存:3776kb
  • [2022-10-31 04:04:07]
  • 提交

answer

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <cassert>
#include <map>
#include <numeric>
#include <cstring>
#include <set>
#include <ctime>
#include <queue>
#include <cmath>
#include <iomanip>
#include <iterator>
#include <bitset>
#include <unordered_map>
#include <complex>
#include <unordered_set>
#include <chrono>
#include <random>
#include <array>
#include <functional>
#include <random>

using namespace std;

int R, C;
int bestDist, ansP, ansI, ansJ, ansC;

bool check(int p, int i, int j, int steps) {
    long long target = 1LL * (i - 1) * C + j - 1;
    p --;
    for (int pos = 0; pos < R * C; pos ++) {
        long long aux = pos, cntSteps = steps;
        while (cntSteps --)
            aux = 1LL * p * R + aux / C;
        if (aux != target)
            return 0;
    }
    return 1;
}

int mod(int x) {
    if (x < 0) return -x;
    return x;
}

int minDist(int i, int R) {
    if (R % 2 == 1) return mod(i - (R + 1) / 2);
    return min(mod(i - R / 2), mod(i - (R / 2 + 1)));
}

void consider(int p, int i, int j, int steps) {
    int dist = minDist(i + 1, R) + minDist(j + 1, C);
    //int dist = (i <= (R - 1) / 2 ? (R - 1) / 2 - i : i - (R / 2)) + (j <= (C - 1) / 2 ? (C - 1) / 2 - j : j - (C / 2));
    if (dist < bestDist || (dist == bestDist && p < ansP)) {
        bestDist = dist;
        ansI = i;
        ansJ = j;
        ansP = p;
        ansC = steps;
    }
}

void tryP(int p) {
    long long beta = 1LL * p * R;
    long long l = 0, r = 1LL * R * C - 1;
    int steps = 0;
    //printf("%d: [%lld, %lld]\n", p, l, r);
    while (l < r) {
        long long newL = beta + l / C, newR = beta + r / C;
        if (newL == l && newR == r)
            return ;
        if (newL < l || newR > r)
            return ;
        l = newL, r = newR;
        steps ++;
        //printf("[%lld, %lld]\n", l, r);
    }
    consider(p, l / C, l % C, steps);
}

int main() {
    //freopen("../input", "r", stdin);
    //freopen("../output", "w", stdout);

    scanf ("%d %d", &R, &C);
    bestDist = 4 * R + 4 * C + 1, ansP = -1, ansI = -1, ansJ = -1, ansC = -1;
    for (int p=0; p + 1<C; p++)
        tryP(p);
    /*for (int p=0; p + 1<C; p++) {
        int beta = p * R;
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++) {
                int l = i * C + j, r = l;
                if (beta > l || beta + R <= l)
                    continue;
                int steps = 0;
                bool ok = 1;
                if (i == 3 && j == 1 && p == 1)
                    printf("[%d, %d]\n", l, r);
                while (l > 0 || r < R * C - 1) {
                    steps++;
                    int newL = max(l - beta, 0) * C;
                    int newR = min(R * C - 1, r * C + (C - 1) - beta);
                    if (newL > l || newR < r || (newL == l && l != 0) || (newR == r && r + 1 != R * C)) {
                        ok = 0;
                        break;
                    }
                    l = newL, r = newR;
                    if (i == 3 && j == 1 && p == 1)
                        printf("[%d, %d]\n", newL, newR);
                }
                if (ok && steps) {
                    consider(p, i, j, steps);
                }
            }
    }*/
    printf("%d %d %d %d\n", ansP + 1, ansI + 1, ansJ + 1, ansC);
    //assert(check(ansP + 1, ansI + 1, ansJ + 1, ansC));
    return 0;
}

/*const int seed = time (0);
mt19937 gen (seed);
long long getRand(long long a, long long b) {return uniform_int_distribution < long long > (a, b) (gen);}*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 43ms
memory: 3636kb

input:

6666 966364

output:

473832 3269 483163 2

result:

ok single line: '473832 3269 483163 2'

Test #2:

score: 0
Accepted
time: 45ms
memory: 3696kb

input:

36 906986

output:

12598 1 453493 2

result:

ok single line: '12598 1 453493 2'

Test #3:

score: 0
Accepted
time: 17ms
memory: 3660kb

input:

704877 297616

output:

148803 352426 140980 3

result:

ok single line: '148803 352426 140980 3'

Test #4:

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

input:

1000000 1000000

output:

500000 500000 500000 2

result:

ok single line: '500000 500000 500000 2'

Test #5:

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

input:

2 2

output:

1 1 1 2

result:

ok single line: '1 1 1 2'

Test #6:

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

input:

1000000 2

output:

1 1 1 21

result:

ok single line: '1 1 1 21'

Test #7:

score: 0
Accepted
time: 46ms
memory: 3768kb

input:

2 1000000

output:

250001 1 500001 2

result:

ok single line: '250001 1 500001 2'

Test #8:

score: 0
Accepted
time: 34ms
memory: 3664kb

input:

985391 511611

output:

255806 492696 255806 3

result:

ok single line: '255806 492696 255806 3'

Test #9:

score: 0
Accepted
time: 34ms
memory: 3664kb

input:

435766 614914

output:

304739 215957 307481 2

result:

ok single line: '304739 215957 307481 2'

Test #10:

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

input:

818196 58

output:

29 401921 49 5

result:

ok single line: '29 401921 49 5'

Test #11:

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

input:

401765 19

output:

10 200883 10 6

result:

ok single line: '10 200883 10 6'

Test #12:

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

input:

95 912669

output:

456335 48 456335 2

result:

ok single line: '456335 48 456335 2'

Test #13:

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

input:

81 429950

output:

2655 1 214975 2

result:

ok single line: '2655 1 214975 2'

Test #14:

score: 0
Accepted
time: 60ms
memory: 3572kb

input:

999956 999959

output:

249991 249990 499979 3

result:

ok single line: '249991 249990 499979 3'

Test #15:

score: 0
Accepted
time: 63ms
memory: 3632kb

input:

999935 999946

output:

449976 449971 499976 3

result:

ok single line: '449976 449971 499976 3'

Test #16:

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

input:

999951 999952

output:

1 1 1 2

result:

ok single line: '1 1 1 2'

Test #17:

score: 0
Accepted
time: 11ms
memory: 3768kb

input:

106352 224337

output:

112111 53149 112993 2

result:

ok single line: '112111 53149 112993 2'

Test #18:

score: 0
Accepted
time: 48ms
memory: 3772kb

input:

651870 786333

output:

392936 325744 393775 2

result:

ok single line: '392936 325744 393775 2'

Test #19:

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

input:

838522 972888

output:

486249 419093 486853 2

result:

ok single line: '486249 419093 486853 2'