QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#546695 | #6607. Rise of Shadows | ucup-team1001# | TL | 1ms | 3720kb | C++20 | 3.3kb | 2024-09-04 11:47:09 | 2024-09-04 11:47:10 |
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 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