QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#94729#2160. Cardiology8BQube#AC ✓28ms3460kbC++202.2kb2023-04-07 17:06:032023-04-07 17:06:06

Judging History

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

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

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define pb push_back
#define ALL(v) v.begin(), v.end()

ll floor(ll a, ll b) {
    return a / b - (a % b && a < 0 ^ b < 0);
}

ll r, c;

ll dis(pii p1, pii p2) {
    return abs(p1.X - p2.X) + abs(p1.Y - p2.Y); 
}

vector<pll> cal(pll rng, int p) {
    pii s = {rng.X / c, rng.X % c};
    pii t = {rng.Y / c, rng.Y % c};
    vector<pii> hei;
    if (s.Y > 0)
        hei.pb({s.X + 1, t.X});
    if (t.Y < c - 1)
        hei.pb({s.X, t.X - 1});
    if (s.Y <= t.Y)
        hei.pb({s.X, t.X});
    if (s.Y > t.Y + 1)
        hei.pb({s.X + 1, t.X - 1});
    vector<pll> ret;
    for (auto [x, y] : hei) {
        if (x <= y)
            ret.pb({(p - 1) * r + x, (p - 1) * r + y}); 
    }
    return ret;
}


int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> r >> c;
    vector<pii> cent; 
    for (int i = (r + 1) / 2; i <= (r + 2) / 2; i++)
        for (int j = (c + 1) / 2; j <= (c + 2) / 2; j++)
            cent.pb({i, j});

    ll p = -1, mindis = 123456789, px = -1, py = -1;
    for (int i = 1; i <= c; i++) {
        ll s = i * r + (c - r);  
        if (s <= 0) continue;
        ll lb = floor((s - c - 1), (c - 1));
        ll rb = (s - 1) / (c - 1);
        lb = max(lb, 0LL);
        rb = min(rb, r);
        if (rb - lb != 1) continue;
        ll x = rb, y = s - (c - 1) * x;
        for (auto pt : cent)
            if (dis(pt, {x, y}) < mindis)
                mindis = dis(pt, {x, y}), p = i, px = x, py = y;
    }

    assert(p != -1);

    cout << p << " " << px << " " << py << " ";

    vector<pll> v;
    v.pb({r * (p - 1), r * p - 1});

    int tt = 1;

    while (true) {
        if (SZ(v) == 1 && v[0].X == v[0].Y) {
            ll t = v[0].X;
            ll x = t / c + 1;
            ll y = t % c + 1;
            assert(x == px && y == py);
            break;
        }
        vector<pll> res;
        for (auto rng : v) {
            auto tmp = cal(rng, p);
            for (auto nrng : tmp)
                res.pb(nrng);
        }
        sort(ALL(res));
        res.resize(unique(ALL(res)) - res.begin());
        v = res;
        tt++;
    }
    cout << tt << endl;
}

详细

Test #1:

score: 100
Accepted
time: 28ms
memory: 3460kb

input:

6666 966364

output:

473832 3269 483163 2

result:

ok single line: '473832 3269 483163 2'

Test #2:

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

input:

36 906986

output:

12598 1 453493 2

result:

ok single line: '12598 1 453493 2'

Test #3:

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

input:

704877 297616

output:

148803 352426 140980 3

result:

ok single line: '148803 352426 140980 3'

Test #4:

score: 0
Accepted
time: 28ms
memory: 3348kb

input:

1000000 1000000

output:

500000 500000 500000 2

result:

ok single line: '500000 500000 500000 2'

Test #5:

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

input:

2 2

output:

1 1 1 2

result:

ok single line: '1 1 1 2'

Test #6:

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

input:

1000000 2

output:

1 1 1 21

result:

ok single line: '1 1 1 21'

Test #7:

score: 0
Accepted
time: 28ms
memory: 3328kb

input:

2 1000000

output:

250001 1 500001 2

result:

ok single line: '250001 1 500001 2'

Test #8:

score: 0
Accepted
time: 13ms
memory: 3404kb

input:

985391 511611

output:

255806 492696 255806 3

result:

ok single line: '255806 492696 255806 3'

Test #9:

score: 0
Accepted
time: 14ms
memory: 3456kb

input:

435766 614914

output:

304739 215957 307481 2

result:

ok single line: '304739 215957 307481 2'

Test #10:

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

input:

818196 58

output:

29 401921 49 5

result:

ok single line: '29 401921 49 5'

Test #11:

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

input:

401765 19

output:

10 200883 10 6

result:

ok single line: '10 200883 10 6'

Test #12:

score: 0
Accepted
time: 20ms
memory: 3460kb

input:

95 912669

output:

456335 48 456335 2

result:

ok single line: '456335 48 456335 2'

Test #13:

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

input:

81 429950

output:

2655 1 214975 2

result:

ok single line: '2655 1 214975 2'

Test #14:

score: 0
Accepted
time: 24ms
memory: 3372kb

input:

999956 999959

output:

249991 249990 499979 3

result:

ok single line: '249991 249990 499979 3'

Test #15:

score: 0
Accepted
time: 24ms
memory: 3460kb

input:

999935 999946

output:

449976 449971 499976 3

result:

ok single line: '449976 449971 499976 3'

Test #16:

score: 0
Accepted
time: 15ms
memory: 3388kb

input:

999951 999952

output:

1 1 1 2

result:

ok single line: '1 1 1 2'

Test #17:

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

input:

106352 224337

output:

112111 53149 112993 2

result:

ok single line: '112111 53149 112993 2'

Test #18:

score: 0
Accepted
time: 19ms
memory: 3404kb

input:

651870 786333

output:

392936 325744 393775 2

result:

ok single line: '392936 325744 393775 2'

Test #19:

score: 0
Accepted
time: 27ms
memory: 3404kb

input:

838522 972888

output:

486249 419093 486853 2

result:

ok single line: '486249 419093 486853 2'