QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#59620 | #2160. Cardiology | losPatrons# | AC ✓ | 63ms | 3776kb | C++14 | 3.6kb | 2022-10-31 04:04:07 | 2022-10-31 04:04:08 |
Judging History
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'