QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#60444 | #2160. Cardiology | fstqwq# | AC ✓ | 84ms | 3452kb | C++20 | 1.7kb | 2022-11-04 19:14:03 | 2022-11-04 19:14:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct point {
int x, y;
};
int dis(point a, point b) {
return abs(a.x - b.x) + abs(a.y - b.y);
}
ll r, c;
pair<int, ll> getstatic(ll offset, ll st) {
auto cur = st;
int fl = 0;
while (true) {
auto nxt = (cur + offset) / c;
if ((st && nxt > cur) || (!st && nxt < cur)) {
fl = -1;
break;
}
if (nxt == cur) {
break;
}
cur = nxt;
fl++;
// cout << "offset = " << offset << " st = " << st << " cur = " << cur << endl;
}
return {fl, cur};
}
int main() {
cin >> r >> c;
vector<int> xs, ys;
if (r & 1) xs.push_back(r / 2);
else xs.push_back(r / 2), xs.push_back(r / 2 - 1);
if (c & 1) ys.push_back(c / 2);
else ys.push_back(c / 2), ys.push_back(c / 2 - 1);
vector<point> vec;
for (auto x : xs)
for (auto y : ys)
vec.push_back({x, y});
auto getdis = [&](point x) {
int mindis = r + c;
for (auto p : vec)
mindis = min(mindis, dis(x, p));
return mindis;
};
// for (auto [x, y] : vec) cout << x << ',' << y << endl;
vector<int> ans = {1919810, 1919810, -1, -1, 1919810}; // [dis, p, i, j, s]
for (ll p = 0; p < c; p++) {
ll cur = r - 1;
// cout << p << ": " << endl;
auto [fl1, k1] = getstatic(p * r, r - 1);
auto [fl2, k2] = getstatic(p * r, 0);
if (fl1==-1 || fl2==-1 || k1 != k2 || k1 >= r || k2 >= r) continue;
point fuck = {k1, (k1 + p * r) % c};
// cout << p << ": ";
vector<int> curans = {getdis(fuck), p, k1, (k1 + p * r) % c, max(fl1, fl2)};
// for (auto i : curans) cout << i << ' ';cout<<endl;
ans = min(ans, curans);
}
cout << ans[1] + 1 << ' ' << ans[2] + 1 << ' ' << ans[3] + 1 << ' ' << ans[4] + 1 << endl;
}
详细
Test #1:
score: 100
Accepted
time: 70ms
memory: 3420kb
input:
6666 966364
output:
473832 3269 483163 2
result:
ok single line: '473832 3269 483163 2'
Test #2:
score: 0
Accepted
time: 66ms
memory: 3424kb
input:
36 906986
output:
12598 1 453493 2
result:
ok single line: '12598 1 453493 2'
Test #3:
score: 0
Accepted
time: 29ms
memory: 3344kb
input:
704877 297616
output:
148803 352426 140980 3
result:
ok single line: '148803 352426 140980 3'
Test #4:
score: 0
Accepted
time: 73ms
memory: 3308kb
input:
1000000 1000000
output:
500000 500000 500000 2
result:
ok single line: '500000 500000 500000 2'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3296kb
input:
2 2
output:
1 1 1 2
result:
ok single line: '1 1 1 2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3264kb
input:
1000000 2
output:
1 1 1 21
result:
ok single line: '1 1 1 21'
Test #7:
score: 0
Accepted
time: 65ms
memory: 3284kb
input:
2 1000000
output:
250001 1 500001 2
result:
ok single line: '250001 1 500001 2'
Test #8:
score: 0
Accepted
time: 44ms
memory: 3420kb
input:
985391 511611
output:
255806 492696 255806 3
result:
ok single line: '255806 492696 255806 3'
Test #9:
score: 0
Accepted
time: 48ms
memory: 3420kb
input:
435766 614914
output:
304739 215957 307481 2
result:
ok single line: '304739 215957 307481 2'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3308kb
input:
818196 58
output:
29 401921 49 5
result:
ok single line: '29 401921 49 5'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3368kb
input:
401765 19
output:
10 200883 10 6
result:
ok single line: '10 200883 10 6'
Test #12:
score: 0
Accepted
time: 65ms
memory: 3280kb
input:
95 912669
output:
456335 48 456335 2
result:
ok single line: '456335 48 456335 2'
Test #13:
score: 0
Accepted
time: 32ms
memory: 3412kb
input:
81 429950
output:
2655 1 214975 2
result:
ok single line: '2655 1 214975 2'
Test #14:
score: 0
Accepted
time: 84ms
memory: 3420kb
input:
999956 999959
output:
249991 249990 499979 3
result:
ok single line: '249991 249990 499979 3'
Test #15:
score: 0
Accepted
time: 80ms
memory: 3452kb
input:
999935 999946
output:
449976 449971 499976 3
result:
ok single line: '449976 449971 499976 3'
Test #16:
score: 0
Accepted
time: 35ms
memory: 3324kb
input:
999951 999952
output:
1 1 1 2
result:
ok single line: '1 1 1 2'
Test #17:
score: 0
Accepted
time: 20ms
memory: 3296kb
input:
106352 224337
output:
112111 53149 112993 2
result:
ok single line: '112111 53149 112993 2'
Test #18:
score: 0
Accepted
time: 64ms
memory: 3372kb
input:
651870 786333
output:
392936 325744 393775 2
result:
ok single line: '392936 325744 393775 2'
Test #19:
score: 0
Accepted
time: 84ms
memory: 3412kb
input:
838522 972888
output:
486249 419093 486853 2
result:
ok single line: '486249 419093 486853 2'