QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#77717#3592. Leaving YharnamevirirAC ✓66ms78176kbC++205.6kb2023-02-15 15:17:212023-02-15 15:17:24

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-15 15:17:24]
  • Judged
  • Verdict: AC
  • Time: 66ms
  • Memory: 78176kb
  • [2023-02-15 15:17:21]
  • Submitted

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'