QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#546587 | #6607. Rise of Shadows | ucup-team1001# | WA | 0ms | 3684kb | C++20 | 2.6kb | 2024-09-04 09:55:09 | 2024-09-04 09:55:13 |
Judging History
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'