QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#546695#6607. Rise of Shadowsucup-team1001#TL 1ms3720kbC++203.3kb2024-09-04 11:47:092024-09-04 11:47:10

Judging History

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

  • [2024-09-04 11:47:10]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3720kb
  • [2024-09-04 11:47:09]
  • 提交

answer

/*

Author: Haze

2024/9/4

*/

#include <bits/stdc++.h>

#define irep(i, l, r) for(int i = (l); i <= (r); ++ i)
#define drep(i, r, l) for(int i = (r); i >= (l); -- i)
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr);
using namespace std;
typedef long long ll;

inline ll readL() {
    ll s = 0;
    bool fl = false;
    char ch = (char) getchar();
    while (!isdigit(ch)) {
        if (ch == '-')fl = true;
        ch = (char) getchar();
    }
    while (isdigit(ch)) {
        s = s * 10 + (ch ^ 48);
        ch = (char) getchar();
    }
    return fl ? -s : s;
}

inline ll read() {
    return (readL());
}

const int mod = 1000000000 + 7;
const int itinf = 1000000999;
const ll llinf = 2e18;
const int N = 500099;

ll work(ll n, ll m, ll s) {
    auto reduce =
            [&m](ll &d, ll &r, ll vd, ll vr) {
                d += vd, r += vr;
                while (r >= m)
                    ++d, r -= m;
                while (r < 0)
                    --d, r += m;
            };
    ll Ld = (- s + m - 1) / m, Lr = (- s + m - 1) % m, Rd = (s) / m, Rr = (s) % m, t1 = (n - 1) / m, t2 = (n - 1) % m;
    ll ans = 0;
    reduce(Ld, Lr, 0, 0);
    for(ll j = 0; j < m; ++ j){
        ans += (min(Rd - Ld + 1, n));
        reduce(Ld, Lr, t1, t2);
        reduce(Rd, Rr, t1, t2);
    }
    return ans;
}

ll solve(ll n, ll m, ll s) {
//    ll n = read(), m = read(), s = readL();
    ll ans = 0;
    ll Rd = s / (n - 1), Ld = 0, Lr = 0, Rr = s % (n - 1), t1 = m / (n - 1), t2 = m % (n - 1);
    Ld = (n - 2 - s) / (n - 1), Lr = (n - 2 - s) - (n - 1) * Ld;
    while (Lr < 0)Lr += n - 1, --Ld;
    while (Lr >= n - 1)Lr -= n - 1, ++Ld;
    auto update =
            [&n](ll &d, ll &r, ll vd, ll vr) {
                d += vd, r += vr;
                while (r >= n - 1)
                    ++d, r -= n - 1;
            };
    cerr << "DDDDDDDDDDDDDDDDDDDDDDDDDDDDD\n";
    update(Ld, Lr, 0, 0);
    update(Rd, Rr, 0, 0);
    for (ll i = 0; i < n; ++i) {
        Rd = min(Rd, m - 1);
        ans += min(m, Rd - Ld + 1);
        update(Ld, Lr, t1, t2);
        update(Rd, Rr, t1, t2);
    }
    cerr << "DDDDDDDDDDDDDDDDDDDDDDDDDDDDD\n";

    return ans;
}


ll solve2(ll n, ll m, ll s) {
    ll ans = 0;
    irep(i, 0, n - 1) {
//        cout << i << endl;
        irep(j, 0, m - 1) {
            ll t1 = (i * m + j) % (n * m), t2 = (j * n) % (n * m);
            ll D = t1 - t2 + n * m;
            D %= (n * m);
            if (min(D, n * m - D) <= s) {
//                cout << j << ' ';
                ++ans;
            }
//            else cerr << i << ' ' << j << endl;
        }
//        cout << endl;
    }
    return ans;
}

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    cout << work(n,m,s);
    return 0;
    srand(time(0));
    int T = 10000000;
    while (T--) {
        ll n, m, s;
        n = rand() % 50 + 2, m = rand() % 50 + 2, s = rand() % (1ll * n * m / 2 + 1);
//        cin >> n >> m >> s;
//        n = 5, m = 5, s = 4;
        ll k1 = work(n, m, s);
        ll k2 = solve2(n, m, s);
        if (k1 != k2) {
            cout << n << ' ' << m << ' ' << s << endl;
            cout << "expected " << k2 << '\n' << "found " << k1;
            return 0;
        } else cout << "Pass\n";
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3596kb

input:

5 5 4

output:

9

result:

ok 1 number(s): "9"

Test #2:

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

input:

3 5 1

output:

3

result:

ok 1 number(s): "3"

Test #3:

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

input:

5 5 0

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

input:

5 5 1

output:

3

result:

ok 1 number(s): "3"

Test #5:

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

input:

5 5 2

output:

5

result:

ok 1 number(s): "5"

Test #6:

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

input:

5 5 3

output:

7

result:

ok 1 number(s): "7"

Test #7:

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

input:

5 5 5

output:

11

result:

ok 1 number(s): "11"

Test #8:

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

input:

5 5 6

output:

13

result:

ok 1 number(s): "13"

Test #9:

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

input:

5 5 7

output:

15

result:

ok 1 number(s): "15"

Test #10:

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

input:

5 5 8

output:

17

result:

ok 1 number(s): "17"

Test #11:

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

input:

5 5 9

output:

19

result:

ok 1 number(s): "19"

Test #12:

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

input:

5 5 10

output:

21

result:

ok 1 number(s): "21"

Test #13:

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

input:

5 5 11

output:

23

result:

ok 1 number(s): "23"

Test #14:

score: -100
Time Limit Exceeded

input:

628383665 981360590 38277030565242771

output:

4294967294

result: