QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#546699 | #6607. Rise of Shadows | ucup-team1001# | AC ✓ | 1972ms | 3692kb | C++20 | 3.3kb | 2024-09-04 11:49:59 | 2024-09-04 11:49:59 |
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() {
ll 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;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3500kb
input:
5 5 4
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
3 5 1
output:
3
result:
ok 1 number(s): "3"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3688kb
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: 3600kb
input:
5 5 2
output:
5
result:
ok 1 number(s): "5"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
5 5 3
output:
7
result:
ok 1 number(s): "7"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
5 5 5
output:
11
result:
ok 1 number(s): "11"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
5 5 6
output:
13
result:
ok 1 number(s): "13"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
5 5 7
output:
15
result:
ok 1 number(s): "15"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
5 5 8
output:
17
result:
ok 1 number(s): "17"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
5 5 9
output:
19
result:
ok 1 number(s): "19"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
5 5 10
output:
21
result:
ok 1 number(s): "21"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
5 5 11
output:
23
result:
ok 1 number(s): "23"
Test #14:
score: 0
Accepted
time: 1972ms
memory: 3596kb
input:
628383665 981360590 38277030565242771
output:
76554061130485542
result:
ok 1 number(s): "76554061130485542"
Test #15:
score: 0
Accepted
time: 1090ms
memory: 3536kb
input:
676930653 505160105 41362516096876079
output:
82725032193752159
result:
ok 1 number(s): "82725032193752159"
Test #16:
score: 0
Accepted
time: 489ms
memory: 3688kb
input:
25827353 275447123 1324720119649964
output:
2649440239299929
result:
ok 1 number(s): "2649440239299929"
Test #17:
score: 0
Accepted
time: 1581ms
memory: 3600kb
input:
685771262 932217613 123112482185767276
output:
246224964371534553
result:
ok 1 number(s): "246224964371534553"
Test #18:
score: 0
Accepted
time: 1839ms
memory: 3560kb
input:
374747225 918729346 88768965881806893
output:
177537931763613786
result:
ok 1 number(s): "177537931763613786"
Test #19:
score: 0
Accepted
time: 1009ms
memory: 3668kb
input:
555840712 538345320 96677957058873941
output:
193355914117747881
result:
ok 1 number(s): "193355914117747881"
Test #20:
score: 0
Accepted
time: 1474ms
memory: 3608kb
input:
830931527 850427591 269919308342575627
output:
539838616685151255
result:
ok 1 number(s): "539838616685151255"
Test #21:
score: 0
Accepted
time: 824ms
memory: 3496kb
input:
467390962 505967360 3011015076837250
output:
6022030153674501
result:
ok 1 number(s): "6022030153674501"
Test #22:
score: 0
Accepted
time: 127ms
memory: 3612kb
input:
575948541 66100036 12663442893218340
output:
25326885786436684
result:
ok 1 number(s): "25326885786436684"
Test #23:
score: 0
Accepted
time: 1014ms
memory: 3608kb
input:
663217337 503323079 132819810249581573
output:
265639620499163147
result:
ok 1 number(s): "265639620499163147"
Test #24:
score: 0
Accepted
time: 1408ms
memory: 3600kb
input:
391395807 703334967 125742012365612971
output:
251484024731225943
result:
ok 1 number(s): "251484024731225943"
Test #25:
score: 0
Accepted
time: 1707ms
memory: 3540kb
input:
914966147 979762626 19974414687500470
output:
39948829375000942
result:
ok 1 number(s): "39948829375000942"
Test #26:
score: 0
Accepted
time: 728ms
memory: 3500kb
input:
254541539 375367245 2737207209565535
output:
5474414419131071
result:
ok 1 number(s): "5474414419131071"
Test #27:
score: 0
Accepted
time: 1851ms
memory: 3620kb
input:
717146311 969520511 60862192208369431
output:
121724384416738863
result:
ok 1 number(s): "121724384416738863"
Test #28:
score: 0
Accepted
time: 1529ms
memory: 3688kb
input:
843136915 902682094 121130375558275200
output:
242260751116550402
result:
ok 1 number(s): "242260751116550402"
Test #29:
score: 0
Accepted
time: 1449ms
memory: 3544kb
input:
712987433 880506334 177850255535317709
output:
355700511070635418
result:
ok 1 number(s): "355700511070635418"
Test #30:
score: 0
Accepted
time: 543ms
memory: 3612kb
input:
8906844 290277920 436178088836242
output:
872356177672485
result:
ok 1 number(s): "872356177672485"
Test #31:
score: 0
Accepted
time: 798ms
memory: 3500kb
input:
455438603 489786671 52188434220052643
output:
104376868440105287
result:
ok 1 number(s): "104376868440105287"
Test #32:
score: 0
Accepted
time: 543ms
memory: 3628kb
input:
580699409 283017980 59899200393498592
output:
119798400786997188
result:
ok 1 number(s): "119798400786997188"
Test #33:
score: 0
Accepted
time: 1566ms
memory: 3684kb
input:
988201298 818909285 347748376469605433
output:
695496752939210867
result:
ok 1 number(s): "695496752939210867"
Test #34:
score: 0
Accepted
time: 1726ms
memory: 3684kb
input:
2 1000000000 3183098
output:
6366197
result:
ok 1 number(s): "6366197"
Test #35:
score: 0
Accepted
time: 1566ms
memory: 3532kb
input:
1000000000 1000000000 1591549430918953
output:
3183098861837907
result:
ok 1 number(s): "3183098861837907"
Test #36:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
1000000000 2 3183098
output:
6366197
result:
ok 1 number(s): "6366197"
Test #37:
score: 0
Accepted
time: 1142ms
memory: 3604kb
input:
165361885 614103002 161620619208607
output:
323241238417214
result:
ok 1 number(s): "323241238417214"
Test #38:
score: 0
Accepted
time: 1241ms
memory: 3532kb
input:
338206415 692137513 372558400738657
output:
745116801477315
result:
ok 1 number(s): "745116801477315"
Test #39:
score: 0
Accepted
time: 893ms
memory: 3688kb
input:
519570752 533307715 441004167445656
output:
882008334891313
result:
ok 1 number(s): "882008334891313"
Test #40:
score: 0
Accepted
time: 324ms
memory: 3688kb
input:
181585050 166789976 48202567091012
output:
96405134182025
result:
ok 1 number(s): "96405134182025"
Test #41:
score: 0
Accepted
time: 1663ms
memory: 3600kb
input:
971564186 857865148 1326510382022331
output:
2653020764044663
result:
ok 1 number(s): "2653020764044663"
Test #42:
score: 0
Accepted
time: 822ms
memory: 3628kb
input:
125110676 387495173 77157971109606
output:
154315942219213
result:
ok 1 number(s): "154315942219213"
Test #43:
score: 0
Accepted
time: 858ms
memory: 3536kb
input:
474474035 438644531 331241926473877
output:
662483852947755
result:
ok 1 number(s): "662483852947755"
Test #44:
score: 0
Accepted
time: 1381ms
memory: 3668kb
input:
916476697 633083096 923426377518472
output:
1846852755036952
result:
ok 1 number(s): "1846852755036952"
Test #45:
score: 0
Accepted
time: 1527ms
memory: 3612kb
input:
706252238 926738795 327089769325054709
output:
654179538650109419
result:
ok 1 number(s): "654179538650109419"
Test #46:
score: 0
Accepted
time: 457ms
memory: 3604kb
input:
792979334 240371723 95256588883570042
output:
190513177767140085
result:
ok 1 number(s): "190513177767140085"
Test #47:
score: 0
Accepted
time: 611ms
memory: 3628kb
input:
442269400 287359100 63512853729212727
output:
127025707458425455
result:
ok 1 number(s): "127025707458425455"
Test #48:
score: 0
Accepted
time: 1005ms
memory: 3692kb
input:
91094881 502894637 22893951411972195
output:
45787902823944391
result:
ok 1 number(s): "45787902823944391"
Test #49:
score: 0
Accepted
time: 994ms
memory: 3604kb
input:
138792107 509615876 35347401879901453
output:
70694803759802906
result:
ok 1 number(s): "70694803759802906"
Test #50:
score: 0
Accepted
time: 410ms
memory: 3540kb
input:
492910976 255958369 63050364679182872
output:
126100729358365745
result:
ok 1 number(s): "126100729358365745"
Test #51:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
86 46 862
output:
1725
result:
ok 1 number(s): "1725"
Test #52:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
55 34 529
output:
1058
result:
ok 1 number(s): "1058"
Test #53:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
20 65 376
output:
753
result:
ok 1 number(s): "753"
Test #54:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
29 47 483
output:
967
result:
ok 1 number(s): "967"
Test #55:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
35 29 486
output:
973
result:
ok 1 number(s): "973"
Test #56:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
73 65 211
output:
423
result:
ok 1 number(s): "423"
Test #57:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
92 6 60
output:
121
result:
ok 1 number(s): "121"
Test #58:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
21 48 176
output:
356
result:
ok 1 number(s): "356"
Test #59:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
74 2 34
output:
69
result:
ok 1 number(s): "69"
Test #60:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
42 83 1043
output:
2087
result:
ok 1 number(s): "2087"
Test #61:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
5 5 12
output:
25
result:
ok 1 number(s): "25"
Test #62:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
5000 5000 12493663
output:
24987327
result:
ok 1 number(s): "24987327"
Test #63:
score: 0
Accepted
time: 2ms
memory: 3532kb
input:
10 1000000 4997465
output:
9994931
result:
ok 1 number(s): "9994931"
Test #64:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
1000000 10 4997465
output:
9994931
result:
ok 1 number(s): "9994931"
Test #65:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
10000 10000 49974652
output:
99949305
result:
ok 1 number(s): "99949305"
Test #66:
score: 0
Accepted
time: 173ms
memory: 3612kb
input:
2 100000000 99949304
output:
199898609
result:
ok 1 number(s): "199898609"
Test #67:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
100000000 2 99949304
output:
199898609
result:
ok 1 number(s): "199898609"
Test #68:
score: 0
Accepted
time: 173ms
memory: 3684kb
input:
2 100000000 318309
output:
636619
result:
ok 1 number(s): "636619"
Test #69:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
100000000 2 318309
output:
636619
result:
ok 1 number(s): "636619"
Test #70:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
10000 10000 159154
output:
318309
result:
ok 1 number(s): "318309"
Test #71:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
2 2 0
output:
1
result:
ok 1 number(s): "1"
Test #72:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
2 2 1
output:
3
result:
ok 1 number(s): "3"
Test #73:
score: 0
Accepted
time: 1560ms
memory: 3500kb
input:
1000000000 1000000000 499746521308551373
output:
999493042617102747
result:
ok 1 number(s): "999493042617102747"
Test #74:
score: 0
Accepted
time: 1571ms
memory: 3596kb
input:
1000000000 1000000000 3183098861837906
output:
6366197723675813
result:
ok 1 number(s): "6366197723675813"
Test #75:
score: 0
Accepted
time: 1565ms
memory: 3512kb
input:
1000000000 1000000000 4774648292756860
output:
9549296585513721
result:
ok 1 number(s): "9549296585513721"
Test #76:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
1000000000 2 6366197
output:
12732395
result:
ok 1 number(s): "12732395"
Test #77:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
100000000 2 636619
output:
1273239
result:
ok 1 number(s): "1273239"
Test #78:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
1000000000 2 9549296
output:
19098593
result:
ok 1 number(s): "19098593"
Test #79:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
99999999 2 636619
output:
1273238
result:
ok 1 number(s): "1273238"
Test #80:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
99999999 2 954929
output:
1909858
result:
ok 1 number(s): "1909858"
Test #81:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
99999999 2 99630993
output:
199261986
result:
ok 1 number(s): "199261986"
Test #82:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
99999999 2 99312683
output:
198625366
result:
ok 1 number(s): "198625366"
Test #83:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
6 60 0
output:
5
result:
ok 1 number(s): "5"
Test #84:
score: 0
Accepted
time: 1568ms
memory: 3532kb
input:
1000000000 1000000000 500000000000000000
output:
1000000000000000000
result:
ok 1 number(s): "1000000000000000000"
Test #85:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
100 9900 0
output:
99
result:
ok 1 number(s): "99"
Test #86:
score: 0
Accepted
time: 175ms
memory: 3684kb
input:
100000 99999000 25
output:
99999
result:
ok 1 number(s): "99999"
Test #87:
score: 0
Accepted
time: 1726ms
memory: 3552kb
input:
1000000000 999999999 0
output:
999999999
result:
ok 1 number(s): "999999999"
Test #88:
score: 0
Accepted
time: 1725ms
memory: 3688kb
input:
1000000000 999999999 114514
output:
999999999
result:
ok 1 number(s): "999999999"
Test #89:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
1000000 200000 100000000000
output:
200000000000
result:
ok 1 number(s): "200000000000"
Test #90:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
100 200 10000
output:
20000
result:
ok 1 number(s): "20000"
Test #91:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
2 2 2
output:
4
result:
ok 1 number(s): "4"
Test #92:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
12 60 0
output:
1
result:
ok 1 number(s): "1"
Test #93:
score: 0
Accepted
time: 1566ms
memory: 3616kb
input:
999999999 1000000000 499999999500000000
output:
999999999000000000
result:
ok 1 number(s): "999999999000000000"
Test #94:
score: 0
Accepted
time: 1730ms
memory: 3496kb
input:
1000000000 999999999 499999999500000000
output:
999999999000000000
result:
ok 1 number(s): "999999999000000000"
Test #95:
score: 0
Accepted
time: 981ms
memory: 3612kb
input:
149401225 503585172 37618120794317850
output:
75236241588635700
result:
ok 1 number(s): "75236241588635700"
Test #96:
score: 0
Accepted
time: 309ms
memory: 3536kb
input:
247171640 150377151 18584483515598820
output:
37168967031197640
result:
ok 1 number(s): "37168967031197640"
Test #97:
score: 0
Accepted
time: 882ms
memory: 3608kb
input:
478453199 543858390 130105393249244805
output:
260210786498489610
result:
ok 1 number(s): "260210786498489610"