QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#546587#6607. Rise of Shadowsucup-team1001#WA 0ms3684kbC++202.6kb2024-09-04 09:55:092024-09-04 09:55:13

Judging History

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

  • [2024-09-04 09:55:13]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3684kb
  • [2024-09-04 09:55: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 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;
    };

    for(ll i = 0; i < n; ++ i){
        Rd = min(Rd, m - 1);
//        cerr << Ld << ' ' << Rd << endl;
        ans += (min(Rd, m - 1) - max(Ld, 0ll) + 1);
        update(Ld, Lr, t1, t2);
        update(Rd, Rr, t1, t2);
    }
    return ans;
}


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

int main() {
    ll n = read(), m = read(), s = read();
    cout << solve(n, m, s);
    return 0;
    // IOS
//    cout << solve(10, 10, 22) << endl;
//    cout << solve2(10, 10, 22);
//    return 0;
//    srand(time(0));
//    int T = 10000000;
//    while (T--) {
//        ll n, m, s;
//        n = rand() % 100000 + 2, m = rand() % 100000 + 2, s = rand() % (1ll * n * m / 2);
////        cin >> n >> m >> s;
//        ll k1 = solve(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: 0ms
memory: 3540kb

input:

5 5 4

output:

9

result:

ok 1 number(s): "9"

Test #2:

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

input:

3 5 1

output:

3

result:

ok 1 number(s): "3"

Test #3:

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

input:

5 5 0

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

input:

5 5 1

output:

3

result:

ok 1 number(s): "3"

Test #5:

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

input:

5 5 2

output:

5

result:

ok 1 number(s): "5"

Test #6:

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

input:

5 5 3

output:

7

result:

ok 1 number(s): "7"

Test #7:

score: -100
Wrong Answer
time: 0ms
memory: 3496kb

input:

5 5 5

output:

10

result:

wrong answer 1st numbers differ - expected: '11', found: '10'