QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#77717 | #3592. Leaving Yharnam | evirir | AC ✓ | 66ms | 78176kb | C++20 | 5.6kb | 2023-02-15 15:17:21 | 2023-02-15 15:17:24 |
Judging History
answer
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")
#define watch(x) cout << (#x) << "=" << (x) << '\n'
#define mset(d, val) memset(d, val, sizeof(d))
#define setp(x) cout << fixed << setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i, a, b) for (int i = (a); i < (b); i++)
#define fore(i, a, b) for (int i = (a); i <= (b); i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
// template<typename T>
// using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void SD(int t = 0) { cout << "PASSED " << t << endl; }
ostream &operator<<(ostream &out, ii x)
{
out << "(" << x.F << "," << x.S << ")";
return out;
}
template <typename T>
void amax(T &a, T b) { a = max(a, b); }
template <typename T>
void amin(T &a, T b) { a = min(a, b); }
const ll INF = ll(1e18);
const int MOD = 1e9 + 7;
vector<ll> fact, ifact, inv, pow2;
ll add(ll a, ll b, ll m = MOD)
{
a += b;
if (abs(a) >= m)
a %= m;
if (a < 0)
a += m;
return a;
}
ll mult(ll a, ll b, ll m = MOD)
{
if (abs(a) >= m)
a %= m;
if (abs(b) >= m)
b %= m;
a *= b;
if (abs(a) >= m)
a %= m;
if (a < 0)
a += m;
return a;
}
void radd(ll &a, ll b, ll m = MOD) { a = add(a, b, m); }
void rmult(ll &a, ll b, ll m = MOD) { a = mult(a, b, m); }
ll pw(ll a, ll b, ll m = MOD)
{
assert(b >= 0); // can return 0 if desired
if (abs(a) >= m)
a %= m;
if (a == 0 && b == 0)
return 0; // value of 0^0
ll r = 1;
while (b)
{
if (b & 1)
r = mult(r, a, m);
a = mult(a, a, m);
b >>= 1;
}
return r;
}
ll inverse(ll a, ll m = MOD)
{
return pw(a, m - 2);
}
ll choose(ll a, ll b)
{
assert(min(a, b) >= 0);
if (a < b)
return 0;
if (b == 0)
return 1;
if (a == b)
return 1;
return mult(fact[a], mult(ifact[b], ifact[a - b]));
}
void init(ll _n)
{
fact.clear();
ifact.clear();
inv.clear();
pow2.clear();
fact.resize(_n + 1);
ifact.resize(_n + 1);
inv.resize(_n + 1);
pow2.resize(_n + 1);
pow2[0] = 1;
ifact[0] = 1;
fact[0] = 1;
for (int i = 1; i <= _n; i++)
{
pow2[i] = add(pow2[i - 1], pow2[i - 1]);
fact[i] = mult(fact[i - 1], i);
}
ifact[_n] = inverse(fact[_n]);
for (int i = _n - 1; i >= 1; i--)
{
ifact[i] = mult(ifact[i + 1], i + 1);
}
for (int i = 1; i <= _n; i++)
{
inv[i] = mult(fact[i - 1], ifact[i]);
}
}
const bool DEBUG = 0;
const int MAXN = 1000005;
const int LG = 21;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n, G, I, E;
cin >> n >> G >> I >> E;
G = min(G, n * 2);
E = min(E, n * 2 - G);
I = min(I, n * 2 - G - E);
init(n * 3);
ll total_value = 0;
ll total_ways = mult(choose(2 * n, G), fact[G]);
for (ll gen_pair_count = max(0LL, G - n); gen_pair_count <= min(n, G / 2); gen_pair_count++)
{
vector<ll> seat_count(3, 0);
seat_count[2] = gen_pair_count;
seat_count[1] = G - gen_pair_count * 2;
seat_count[0] = n - seat_count[2] - seat_count[1];
ll cur_ways = mult(choose(n, seat_count[2]), choose(n - seat_count[2], seat_count[1]));
rmult(cur_ways, fact[G]);
rmult(cur_ways, pow2[seat_count[1]]);
ll cur_value = G;
// extroverts
bool single_are_extro;
if (E <= seat_count[1])
{
single_are_extro = false;
radd(cur_value, E);
seat_count[1] -= E;
seat_count[2] += E;
}
else
{
single_are_extro = true;
// seat happy extroverts
radd(cur_value, seat_count[1]);
ll rem_extro = E - seat_count[1]; // only happily-seatable extros
seat_count[2] += seat_count[1];
seat_count[1] = 0;
// seat remaining extroverts, pairing them
ll new_pair_count = min(seat_count[0], rem_extro / 2);
radd(cur_value, 2 * new_pair_count);
seat_count[2] += new_pair_count;
seat_count[0] -= new_pair_count;
if (rem_extro % 2 == 1)
{
seat_count[1]++;
seat_count[0]--;
}
}
// happy introverts
ll happy_intro_count = min(I, seat_count[0]);
radd(cur_value, happy_intro_count);
seat_count[0] -= happy_intro_count;
seat_count[1] += happy_intro_count;
ll rem_intro = I - happy_intro_count;
// remaining single seats are intro + extro or intro + gen
ll intro_beside_non_intro = min(rem_intro, seat_count[1] - happy_intro_count);
if (single_are_extro)
radd(cur_value, intro_beside_non_intro);
seat_count[1] -= intro_beside_non_intro;
seat_count[2] += intro_beside_non_intro;
rem_intro -= intro_beside_non_intro;
// intros forced to seat beside intros
radd(cur_value, -rem_intro);
radd(total_value, mult(cur_ways, cur_value));
}
cout << mult(total_value, inverse(total_ways)) << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3384kb
input:
1 0 1 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3404kb
input:
10 5 13 11
output:
16
result:
ok single line: '16'
Test #3:
score: 0
Accepted
time: 26ms
memory: 33360kb
input:
324005 203143 770973 565020
output:
648010
result:
ok single line: '648010'
Test #4:
score: 0
Accepted
time: 61ms
memory: 76616kb
input:
783794 966573 337313 49232
output:
658568709
result:
ok single line: '658568709'
Test #5:
score: 0
Accepted
time: 14ms
memory: 23912kb
input:
224046 630433 450997 667681
output:
448092
result:
ok single line: '448092'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3332kb
input:
5 20 2 13
output:
10
result:
ok single line: '10'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3400kb
input:
4 0 10 14
output:
8
result:
ok single line: '8'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3396kb
input:
1 19 17 3
output:
2
result:
ok single line: '2'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3488kb
input:
2 20 19 1
output:
4
result:
ok single line: '4'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3332kb
input:
18 11 4 15
output:
30
result:
ok single line: '30'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3348kb
input:
6 1 13 18
output:
12
result:
ok single line: '12'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3524kb
input:
19 12 2 19
output:
32
result:
ok single line: '32'
Test #13:
score: 0
Accepted
time: 2ms
memory: 3548kb
input:
1 2 5 8
output:
2
result:
ok single line: '2'
Test #14:
score: 0
Accepted
time: 2ms
memory: 3484kb
input:
20 5 2 18
output:
24
result:
ok single line: '24'
Test #15:
score: 0
Accepted
time: 2ms
memory: 3400kb
input:
10 0 11 0
output:
9
result:
ok single line: '9'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3336kb
input:
10 3 9 6
output:
11
result:
ok single line: '11'
Test #17:
score: 0
Accepted
time: 2ms
memory: 3404kb
input:
16 13 13 14
output:
27
result:
ok single line: '27'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3348kb
input:
20 16 12 0
output:
153846178
result:
ok single line: '153846178'
Test #19:
score: 0
Accepted
time: 2ms
memory: 3352kb
input:
20 3 4 3
output:
10
result:
ok single line: '10'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3404kb
input:
8 16 19 14
output:
16
result:
ok single line: '16'
Test #21:
score: 0
Accepted
time: 2ms
memory: 3556kb
input:
17 4 5 11
output:
19
result:
ok single line: '19'
Test #22:
score: 0
Accepted
time: 2ms
memory: 3408kb
input:
8 12 8 13
output:
16
result:
ok single line: '16'
Test #23:
score: 0
Accepted
time: 2ms
memory: 3556kb
input:
19 18 4 18
output:
36
result:
ok single line: '36'
Test #24:
score: 0
Accepted
time: 2ms
memory: 3332kb
input:
5 14 8 0
output:
10
result:
ok single line: '10'
Test #25:
score: 0
Accepted
time: 2ms
memory: 3392kb
input:
2 5 1 17
output:
4
result:
ok single line: '4'
Test #26:
score: 0
Accepted
time: 2ms
memory: 3352kb
input:
2 2 1 0
output:
333333338
result:
ok single line: '333333338'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3328kb
input:
10 1 0 2
output:
2
result:
ok single line: '2'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3408kb
input:
10 17 10 0
output:
17
result:
ok single line: '17'
Test #29:
score: 0
Accepted
time: 2ms
memory: 3408kb
input:
15 2 8 6
output:
16
result:
ok single line: '16'
Test #30:
score: 0
Accepted
time: 2ms
memory: 3524kb
input:
3 4 2 1
output:
5
result:
ok single line: '5'
Test #31:
score: 0
Accepted
time: 2ms
memory: 3396kb
input:
10 18 3 18
output:
20
result:
ok single line: '20'
Test #32:
score: 0
Accepted
time: 2ms
memory: 3488kb
input:
20 18 19 5
output:
23
result:
ok single line: '23'
Test #33:
score: 0
Accepted
time: 2ms
memory: 3396kb
input:
9 2 7 7
output:
11
result:
ok single line: '11'
Test #34:
score: 0
Accepted
time: 2ms
memory: 3488kb
input:
11 12 3 9
output:
21
result:
ok single line: '21'
Test #35:
score: 0
Accepted
time: 2ms
memory: 3332kb
input:
10 8 2 8
output:
18
result:
ok single line: '18'
Test #36:
score: 0
Accepted
time: 2ms
memory: 3392kb
input:
17 11 2 9
output:
22
result:
ok single line: '22'
Test #37:
score: 0
Accepted
time: 2ms
memory: 3396kb
input:
11 10 15 6
output:
16
result:
ok single line: '16'
Test #38:
score: 0
Accepted
time: 0ms
memory: 3396kb
input:
1 14 16 5
output:
2
result:
ok single line: '2'
Test #39:
score: 0
Accepted
time: 0ms
memory: 3388kb
input:
9 8 10 3
output:
11
result:
ok single line: '11'
Test #40:
score: 0
Accepted
time: 2ms
memory: 3516kb
input:
9 8 8 3
output:
11
result:
ok single line: '11'
Test #41:
score: 0
Accepted
time: 2ms
memory: 3392kb
input:
9 1 3 10
output:
13
result:
ok single line: '13'
Test #42:
score: 0
Accepted
time: 2ms
memory: 3488kb
input:
1000 500 0 0
output:
500
result:
ok single line: '500'
Test #43:
score: 0
Accepted
time: 2ms
memory: 3612kb
input:
1000 1000 0 0
output:
1000
result:
ok single line: '1000'
Test #44:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
1000 1500 0 0
output:
1500
result:
ok single line: '1500'
Test #45:
score: 0
Accepted
time: 2ms
memory: 3484kb
input:
1000 2000 0 0
output:
2000
result:
ok single line: '2000'
Test #46:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
1000 2500 0 0
output:
2000
result:
ok single line: '2000'
Test #47:
score: 0
Accepted
time: 2ms
memory: 3432kb
input:
1000 0 500 0
output:
500
result:
ok single line: '500'
Test #48:
score: 0
Accepted
time: 0ms
memory: 3396kb
input:
10 1 18 2
output:
3
result:
ok single line: '3'
Test #49:
score: 0
Accepted
time: 2ms
memory: 3608kb
input:
1000 0 1000 0
output:
1000
result:
ok single line: '1000'
Test #50:
score: 0
Accepted
time: 2ms
memory: 3496kb
input:
1000 0 1500 0
output:
500
result:
ok single line: '500'
Test #51:
score: 0
Accepted
time: 2ms
memory: 3644kb
input:
1000 0 2000 0
output:
0
result:
ok single line: '0'
Test #52:
score: 0
Accepted
time: 2ms
memory: 3488kb
input:
1000 0 2500 0
output:
0
result:
ok single line: '0'
Test #53:
score: 0
Accepted
time: 2ms
memory: 3612kb
input:
1000 0 0 500
output:
500
result:
ok single line: '500'
Test #54:
score: 0
Accepted
time: 2ms
memory: 3488kb
input:
1000 0 0 1000
output:
1000
result:
ok single line: '1000'
Test #55:
score: 0
Accepted
time: 2ms
memory: 3484kb
input:
1000 0 0 1500
output:
1500
result:
ok single line: '1500'
Test #56:
score: 0
Accepted
time: 2ms
memory: 3616kb
input:
1000 0 0 2000
output:
2000
result:
ok single line: '2000'
Test #57:
score: 0
Accepted
time: 2ms
memory: 3640kb
input:
1000 0 0 2500
output:
2000
result:
ok single line: '2000'
Test #58:
score: 0
Accepted
time: 2ms
memory: 3440kb
input:
1000 300 300 0
output:
600
result:
ok single line: '600'
Test #59:
score: 0
Accepted
time: 2ms
memory: 3288kb
input:
1 11 0 11
output:
2
result:
ok single line: '2'
Test #60:
score: 0
Accepted
time: 2ms
memory: 3496kb
input:
1000 500 500 0
output:
1000
result:
ok single line: '1000'
Test #61:
score: 0
Accepted
time: 3ms
memory: 3496kb
input:
1000 700 700 0
output:
158494380
result:
ok single line: '158494380'
Test #62:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
1000 1000 1000 0
output:
1000
result:
ok single line: '1000'
Test #63:
score: 0
Accepted
time: 2ms
memory: 3484kb
input:
1000 1500 1500 0
output:
1500
result:
ok single line: '1500'
Test #64:
score: 0
Accepted
time: 2ms
memory: 3488kb
input:
1000 2000 2000 0
output:
2000
result:
ok single line: '2000'
Test #65:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
1000 300 0 300
output:
600
result:
ok single line: '600'
Test #66:
score: 0
Accepted
time: 2ms
memory: 3480kb
input:
1000 500 0 500
output:
1000
result:
ok single line: '1000'
Test #67:
score: 0
Accepted
time: 2ms
memory: 3484kb
input:
1000 700 0 700
output:
1400
result:
ok single line: '1400'
Test #68:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
1000 1000 0 1000
output:
2000
result:
ok single line: '2000'
Test #69:
score: 0
Accepted
time: 2ms
memory: 3492kb
input:
1000 1500 0 1500
output:
2000
result:
ok single line: '2000'
Test #70:
score: 0
Accepted
time: 2ms
memory: 3392kb
input:
19 12 14 10
output:
24
result:
ok single line: '24'
Test #71:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
1000 2000 0 2000
output:
2000
result:
ok single line: '2000'
Test #72:
score: 0
Accepted
time: 2ms
memory: 3480kb
input:
1000 0 300 300
output:
600
result:
ok single line: '600'
Test #73:
score: 0
Accepted
time: 2ms
memory: 3644kb
input:
1000 0 500 500
output:
1000
result:
ok single line: '1000'
Test #74:
score: 0
Accepted
time: 1ms
memory: 3488kb
input:
1000 0 700 700
output:
1300
result:
ok single line: '1300'
Test #75:
score: 0
Accepted
time: 2ms
memory: 3480kb
input:
1000 0 1000 1000
output:
1000
result:
ok single line: '1000'
Test #76:
score: 0
Accepted
time: 2ms
memory: 3580kb
input:
1000 0 1500 1500
output:
1500
result:
ok single line: '1500'
Test #77:
score: 0
Accepted
time: 2ms
memory: 3484kb
input:
1000 0 2000 2000
output:
2000
result:
ok single line: '2000'
Test #78:
score: 0
Accepted
time: 2ms
memory: 3636kb
input:
2637 6773 9174 1735
output:
5274
result:
ok single line: '5274'
Test #79:
score: 0
Accepted
time: 2ms
memory: 3584kb
input:
2703 8304 3387 1641
output:
5406
result:
ok single line: '5406'
Test #80:
score: 0
Accepted
time: 3ms
memory: 3840kb
input:
6326 8700 3534 6848
output:
12652
result:
ok single line: '12652'
Test #81:
score: 0
Accepted
time: 2ms
memory: 3552kb
input:
15 15 12 17
output:
30
result:
ok single line: '30'
Test #82:
score: 0
Accepted
time: 2ms
memory: 3600kb
input:
2142 6609 4924 4096
output:
4284
result:
ok single line: '4284'
Test #83:
score: 0
Accepted
time: 3ms
memory: 4072kb
input:
9565 8872 6950 5722
output:
14594
result:
ok single line: '14594'
Test #84:
score: 0
Accepted
time: 2ms
memory: 3436kb
input:
547 2715 9932 9784
output:
1094
result:
ok single line: '1094'
Test #85:
score: 0
Accepted
time: 1ms
memory: 3412kb
input:
88 2600 8625 3878
output:
176
result:
ok single line: '176'
Test #86:
score: 0
Accepted
time: 2ms
memory: 3672kb
input:
1661 8169 2242 4146
output:
3322
result:
ok single line: '3322'
Test #87:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
4167 1089 8718 9606
output:
8334
result:
ok single line: '8334'
Test #88:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
4463 553 8538 5105
output:
5658
result:
ok single line: '5658'
Test #89:
score: 0
Accepted
time: 3ms
memory: 3744kb
input:
8142 9612 4922 8312
output:
16284
result:
ok single line: '16284'
Test #90:
score: 0
Accepted
time: 3ms
memory: 3832kb
input:
6612 6829 2173 4699
output:
11528
result:
ok single line: '11528'
Test #91:
score: 0
Accepted
time: 2ms
memory: 3716kb
input:
3435 7847 5234 2646
output:
6870
result:
ok single line: '6870'
Test #92:
score: 0
Accepted
time: 2ms
memory: 3400kb
input:
17 13 18 18
output:
31
result:
ok single line: '31'
Test #93:
score: 0
Accepted
time: 2ms
memory: 3868kb
input:
3425 9920 1367 7901
output:
6850
result:
ok single line: '6850'
Test #94:
score: 0
Accepted
time: 3ms
memory: 4080kb
input:
9741 9676 483 2051
output:
330597298
result:
ok single line: '330597298'
Test #95:
score: 0
Accepted
time: 2ms
memory: 3608kb
input:
2324 2737 5161 8088
output:
4648
result:
ok single line: '4648'
Test #96:
score: 0
Accepted
time: 3ms
memory: 3792kb
input:
6606 1493 824 9179
output:
11496
result:
ok single line: '11496'
Test #97:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
8265 9267 238 7595
output:
16530
result:
ok single line: '16530'
Test #98:
score: 0
Accepted
time: 3ms
memory: 3800kb
input:
6992 6132 164 5228
output:
11524
result:
ok single line: '11524'
Test #99:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
3647 6343 9074 4888
output:
7294
result:
ok single line: '7294'
Test #100:
score: 0
Accepted
time: 66ms
memory: 74552kb
input:
761933 965642 909762 628739
output:
1523866
result:
ok single line: '1523866'
Test #101:
score: 0
Accepted
time: 54ms
memory: 65124kb
input:
661992 436246 405301 690525
output:
1126771
result:
ok single line: '1126771'
Test #102:
score: 0
Accepted
time: 61ms
memory: 78176kb
input:
799120 245571 55209 777457
output:
1078237
result:
ok single line: '1078237'