QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#60181 | #2160. Cardiology | MIT01# | AC ✓ | 73ms | 3784kb | C++17 | 1.7kb | 2022-11-03 10:46:26 | 2022-11-03 10:46:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb emplace_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()
template<typename T> inline bool chkmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
typedef long long LL;
const int oo = 0x3f3f3f3f;
int n, m;
vector<pair<int, int> > centers;
struct answer
{
int p, x, y, s;
answer(): p(-1), x(0), y(0), s(0) { }
answer(int _p, int _x, int _y, int _s): p(_p), x(_x), y(_y), s(_s) { }
inline int dis() const
{
if (!~p) return oo;
int ret = oo;
for (auto u : centers)
chkmin(ret, abs(x - u.x) + abs(y - u.y));
return ret;
}
friend inline bool operator<(const answer &x, const answer &y)
{
int xd = x.dis(), yd = y.dis();
if (xd != yd) return xd < yd;
return x.p < y.p;
}
};
answer work(int x)
{
LL l = 0, r = (LL)n * m - 1;
for (int i = 0; ; ++i)
{
if (r - l == 1 && l / m != r / m) return answer();
if (r - l == 0) return answer(x, l / m, l % m, i);
l = l / m + (LL)x * n;
r = r / m + (LL)x * n;
}
}
int main()
{
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
scanf("%d%d", &n, &m);
REP(i, (n - 1) >> 1, (n >> 1) + 1) REP(j, (m - 1) >> 1, (m >> 1) + 1)
centers.pb(mp(i, j));
answer ans;
REP(i, 0, m)
{
answer tmp = work(i);
chkmin(ans, tmp);
}
printf("%d %d %d %d\n", ans.p + 1, ans.x + 1, ans.y + 1, ans.s);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 50ms
memory: 3744kb
input:
6666 966364
output:
473832 3269 483163 2
result:
ok single line: '473832 3269 483163 2'
Test #2:
score: 0
Accepted
time: 45ms
memory: 3620kb
input:
36 906986
output:
12598 1 453493 2
result:
ok single line: '12598 1 453493 2'
Test #3:
score: 0
Accepted
time: 18ms
memory: 3532kb
input:
704877 297616
output:
148803 352426 140980 3
result:
ok single line: '148803 352426 140980 3'
Test #4:
score: 0
Accepted
time: 45ms
memory: 3528kb
input:
1000000 1000000
output:
500000 500000 500000 2
result:
ok single line: '500000 500000 500000 2'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3520kb
input:
2 2
output:
1 1 1 2
result:
ok single line: '1 1 1 2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
1000000 2
output:
1 1 1 21
result:
ok single line: '1 1 1 21'
Test #7:
score: 0
Accepted
time: 56ms
memory: 3544kb
input:
2 1000000
output:
250001 1 500001 2
result:
ok single line: '250001 1 500001 2'
Test #8:
score: 0
Accepted
time: 34ms
memory: 3524kb
input:
985391 511611
output:
255806 492696 255806 3
result:
ok single line: '255806 492696 255806 3'
Test #9:
score: 0
Accepted
time: 43ms
memory: 3532kb
input:
435766 614914
output:
304739 215957 307481 2
result:
ok single line: '304739 215957 307481 2'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3784kb
input:
818196 58
output:
29 401921 49 5
result:
ok single line: '29 401921 49 5'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3668kb
input:
401765 19
output:
10 200883 10 6
result:
ok single line: '10 200883 10 6'
Test #12:
score: 0
Accepted
time: 45ms
memory: 3584kb
input:
95 912669
output:
456335 48 456335 2
result:
ok single line: '456335 48 456335 2'
Test #13:
score: 0
Accepted
time: 23ms
memory: 3624kb
input:
81 429950
output:
2655 1 214975 2
result:
ok single line: '2655 1 214975 2'
Test #14:
score: 0
Accepted
time: 70ms
memory: 3540kb
input:
999956 999959
output:
249991 249990 499979 3
result:
ok single line: '249991 249990 499979 3'
Test #15:
score: 0
Accepted
time: 73ms
memory: 3536kb
input:
999935 999946
output:
449976 449971 499976 3
result:
ok single line: '449976 449971 499976 3'
Test #16:
score: 0
Accepted
time: 53ms
memory: 3528kb
input:
999951 999952
output:
1 1 1 2
result:
ok single line: '1 1 1 2'
Test #17:
score: 0
Accepted
time: 15ms
memory: 3680kb
input:
106352 224337
output:
112111 53149 112993 2
result:
ok single line: '112111 53149 112993 2'
Test #18:
score: 0
Accepted
time: 52ms
memory: 3544kb
input:
651870 786333
output:
392936 325744 393775 2
result:
ok single line: '392936 325744 393775 2'
Test #19:
score: 0
Accepted
time: 67ms
memory: 3776kb
input:
838522 972888
output:
486249 419093 486853 2
result:
ok single line: '486249 419093 486853 2'