QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#223276#3592. Leaving YharnamatoizAC ✓24ms26960kbC++142.0kb2023-10-21 23:25:132023-10-21 23:25:13

Judging History

This is the latest submission verdict.

  • [2023-10-21 23:25:13]
  • Judged
  • Verdict: AC
  • Time: 24ms
  • Memory: 26960kb
  • [2023-10-21 23:25:13]
  • Submitted

answer

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>

using namespace std;

const int MOD = 1000000007;
const int MAXN = 2000007;

int add(int a, int b) { a += b; return a -= (a >= MOD ? MOD : 0); }
int sub(int a, int b) { a -= b; return a += (a  < 0   ? MOD : 0); }
int mul(int a, int b) { return (int) ((int64_t) a * b % MOD); }
int bpow(int a, int p) {
	int x = 1;
	for (; p; p >>= 1) {
		if (p & 1) x = mul(x, a);
		a = mul(a, a);
	}
	return x;
}

int fact[MAXN], ifact[MAXN], pow2[MAXN], N, G, I, E;
int choose(int n, int k) {
	return mul(fact[n], mul(fact[k], fact[n-k]));
}

int main() {
	cin >> N >> G >> I >> E;
	fact[0] = 1;
	for (int i = 1; i <= 2*N; ++i) fact[i] = mul(fact[i-1], i);
	ifact[2*N] = bpow(fact[2*N], MOD - 2);
	for (int i = N*2-1; i >= 0; --i) ifact[i] = mul(ifact[i+1], i+1);
	pow2[0] = 1;
	for (int i = 1; i <= 2*N; ++i) pow2[i] = add(pow2[i-1], pow2[i-1]);

	G = min(G, N*2);
	E = min(E, N*2-G);
	I = min(I, N*2-G-E);

	int ans = 0;
	for (int a = 0; a <= N; ++a) {
		int b = G - a * 2, c = N - a - b;
		if (b < 0 || c < 0) continue;

		int probAB = 1, score = G;
		probAB = mul(probAB, fact[N]);
		probAB = mul(probAB, ifact[a]);
		probAB = mul(probAB, ifact[b]);
		probAB = mul(probAB, ifact[N-a-b]);
		probAB = mul(probAB, pow2[b]);
		probAB = mul(probAB, ifact[2*N]);
		probAB = mul(probAB, fact[2*N-G]);
		probAB = mul(probAB, fact[G]);

		bool remainingE = 0;
		if (b < E) {
			remainingE = (E-b) & 1;
			score += E - remainingE;
			c -= (E-b) / 2 + remainingE;
			b = remainingE;
		} else {
			b -= E;
			score += E;
		}

		// cout << a << ' ' << b << ' ' << c << " - " << I << endl;
		if (c >= I) {
			score += I;
		} else {
			score += c;
			int rI = I - c;

			if (remainingE) {
				remainingE = 0;
				score += 1;
				--b;
				--rI;
			}
			if (rI > b) score -= rI - b;
		}
		// cout << a << ": " << probAB << ' ' << score << endl;
		ans = add(ans, mul(probAB, score));
	}
	cout << ans << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7816kb

input:

1 0 1 1

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 1ms
memory: 7748kb

input:

10 5 13 11

output:

16

result:

ok single line: '16'

Test #3:

score: 0
Accepted
time: 8ms
memory: 14684kb

input:

324005 203143 770973 565020

output:

648010

result:

ok single line: '648010'

Test #4:

score: 0
Accepted
time: 24ms
memory: 25428kb

input:

783794 966573 337313 49232

output:

658568709

result:

ok single line: '658568709'

Test #5:

score: 0
Accepted
time: 8ms
memory: 14832kb

input:

224046 630433 450997 667681

output:

448092

result:

ok single line: '448092'

Test #6:

score: 0
Accepted
time: 1ms
memory: 7800kb

input:

5 20 2 13

output:

10

result:

ok single line: '10'

Test #7:

score: 0
Accepted
time: 1ms
memory: 7820kb

input:

4 0 10 14

output:

8

result:

ok single line: '8'

Test #8:

score: 0
Accepted
time: 1ms
memory: 7676kb

input:

1 19 17 3

output:

2

result:

ok single line: '2'

Test #9:

score: 0
Accepted
time: 1ms
memory: 7744kb

input:

2 20 19 1

output:

4

result:

ok single line: '4'

Test #10:

score: 0
Accepted
time: 1ms
memory: 7752kb

input:

18 11 4 15

output:

30

result:

ok single line: '30'

Test #11:

score: 0
Accepted
time: 1ms
memory: 7804kb

input:

6 1 13 18

output:

12

result:

ok single line: '12'

Test #12:

score: 0
Accepted
time: 1ms
memory: 7760kb

input:

19 12 2 19

output:

32

result:

ok single line: '32'

Test #13:

score: 0
Accepted
time: 1ms
memory: 7764kb

input:

1 2 5 8

output:

2

result:

ok single line: '2'

Test #14:

score: 0
Accepted
time: 1ms
memory: 7680kb

input:

20 5 2 18

output:

24

result:

ok single line: '24'

Test #15:

score: 0
Accepted
time: 1ms
memory: 7688kb

input:

10 0 11 0

output:

9

result:

ok single line: '9'

Test #16:

score: 0
Accepted
time: 0ms
memory: 7748kb

input:

10 3 9 6

output:

11

result:

ok single line: '11'

Test #17:

score: 0
Accepted
time: 1ms
memory: 7808kb

input:

16 13 13 14

output:

27

result:

ok single line: '27'

Test #18:

score: 0
Accepted
time: 1ms
memory: 7808kb

input:

20 16 12 0

output:

153846178

result:

ok single line: '153846178'

Test #19:

score: 0
Accepted
time: 0ms
memory: 7812kb

input:

20 3 4 3

output:

10

result:

ok single line: '10'

Test #20:

score: 0
Accepted
time: 1ms
memory: 7752kb

input:

8 16 19 14

output:

16

result:

ok single line: '16'

Test #21:

score: 0
Accepted
time: 0ms
memory: 7608kb

input:

17 4 5 11

output:

19

result:

ok single line: '19'

Test #22:

score: 0
Accepted
time: 1ms
memory: 7736kb

input:

8 12 8 13

output:

16

result:

ok single line: '16'

Test #23:

score: 0
Accepted
time: 1ms
memory: 7748kb

input:

19 18 4 18

output:

36

result:

ok single line: '36'

Test #24:

score: 0
Accepted
time: 1ms
memory: 7688kb

input:

5 14 8 0

output:

10

result:

ok single line: '10'

Test #25:

score: 0
Accepted
time: 0ms
memory: 7812kb

input:

2 5 1 17

output:

4

result:

ok single line: '4'

Test #26:

score: 0
Accepted
time: 0ms
memory: 7628kb

input:

2 2 1 0

output:

333333338

result:

ok single line: '333333338'

Test #27:

score: 0
Accepted
time: 1ms
memory: 7632kb

input:

10 1 0 2

output:

2

result:

ok single line: '2'

Test #28:

score: 0
Accepted
time: 1ms
memory: 7812kb

input:

10 17 10 0

output:

17

result:

ok single line: '17'

Test #29:

score: 0
Accepted
time: 1ms
memory: 7680kb

input:

15 2 8 6

output:

16

result:

ok single line: '16'

Test #30:

score: 0
Accepted
time: 1ms
memory: 7816kb

input:

3 4 2 1

output:

5

result:

ok single line: '5'

Test #31:

score: 0
Accepted
time: 1ms
memory: 7748kb

input:

10 18 3 18

output:

20

result:

ok single line: '20'

Test #32:

score: 0
Accepted
time: 1ms
memory: 7748kb

input:

20 18 19 5

output:

23

result:

ok single line: '23'

Test #33:

score: 0
Accepted
time: 1ms
memory: 7748kb

input:

9 2 7 7

output:

11

result:

ok single line: '11'

Test #34:

score: 0
Accepted
time: 1ms
memory: 7764kb

input:

11 12 3 9

output:

21

result:

ok single line: '21'

Test #35:

score: 0
Accepted
time: 1ms
memory: 7748kb

input:

10 8 2 8

output:

18

result:

ok single line: '18'

Test #36:

score: 0
Accepted
time: 1ms
memory: 7680kb

input:

17 11 2 9

output:

22

result:

ok single line: '22'

Test #37:

score: 0
Accepted
time: 0ms
memory: 7820kb

input:

11 10 15 6

output:

16

result:

ok single line: '16'

Test #38:

score: 0
Accepted
time: 1ms
memory: 7768kb

input:

1 14 16 5

output:

2

result:

ok single line: '2'

Test #39:

score: 0
Accepted
time: 1ms
memory: 7748kb

input:

9 8 10 3

output:

11

result:

ok single line: '11'

Test #40:

score: 0
Accepted
time: 0ms
memory: 7832kb

input:

9 8 8 3

output:

11

result:

ok single line: '11'

Test #41:

score: 0
Accepted
time: 1ms
memory: 7808kb

input:

9 1 3 10

output:

13

result:

ok single line: '13'

Test #42:

score: 0
Accepted
time: 0ms
memory: 7688kb

input:

1000 500 0 0

output:

500

result:

ok single line: '500'

Test #43:

score: 0
Accepted
time: 0ms
memory: 7776kb

input:

1000 1000 0 0

output:

1000

result:

ok single line: '1000'

Test #44:

score: 0
Accepted
time: 0ms
memory: 7756kb

input:

1000 1500 0 0

output:

1500

result:

ok single line: '1500'

Test #45:

score: 0
Accepted
time: 1ms
memory: 7812kb

input:

1000 2000 0 0

output:

2000

result:

ok single line: '2000'

Test #46:

score: 0
Accepted
time: 1ms
memory: 7636kb

input:

1000 2500 0 0

output:

2000

result:

ok single line: '2000'

Test #47:

score: 0
Accepted
time: 1ms
memory: 7720kb

input:

1000 0 500 0

output:

500

result:

ok single line: '500'

Test #48:

score: 0
Accepted
time: 1ms
memory: 7812kb

input:

10 1 18 2

output:

3

result:

ok single line: '3'

Test #49:

score: 0
Accepted
time: 1ms
memory: 7756kb

input:

1000 0 1000 0

output:

1000

result:

ok single line: '1000'

Test #50:

score: 0
Accepted
time: 1ms
memory: 7776kb

input:

1000 0 1500 0

output:

500

result:

ok single line: '500'

Test #51:

score: 0
Accepted
time: 1ms
memory: 7836kb

input:

1000 0 2000 0

output:

0

result:

ok single line: '0'

Test #52:

score: 0
Accepted
time: 1ms
memory: 7756kb

input:

1000 0 2500 0

output:

0

result:

ok single line: '0'

Test #53:

score: 0
Accepted
time: 1ms
memory: 7828kb

input:

1000 0 0 500

output:

500

result:

ok single line: '500'

Test #54:

score: 0
Accepted
time: 1ms
memory: 7812kb

input:

1000 0 0 1000

output:

1000

result:

ok single line: '1000'

Test #55:

score: 0
Accepted
time: 1ms
memory: 7752kb

input:

1000 0 0 1500

output:

1500

result:

ok single line: '1500'

Test #56:

score: 0
Accepted
time: 1ms
memory: 7688kb

input:

1000 0 0 2000

output:

2000

result:

ok single line: '2000'

Test #57:

score: 0
Accepted
time: 1ms
memory: 7836kb

input:

1000 0 0 2500

output:

2000

result:

ok single line: '2000'

Test #58:

score: 0
Accepted
time: 1ms
memory: 7776kb

input:

1000 300 300 0

output:

600

result:

ok single line: '600'

Test #59:

score: 0
Accepted
time: 1ms
memory: 7812kb

input:

1 11 0 11

output:

2

result:

ok single line: '2'

Test #60:

score: 0
Accepted
time: 1ms
memory: 7756kb

input:

1000 500 500 0

output:

1000

result:

ok single line: '1000'

Test #61:

score: 0
Accepted
time: 1ms
memory: 7776kb

input:

1000 700 700 0

output:

158494380

result:

ok single line: '158494380'

Test #62:

score: 0
Accepted
time: 1ms
memory: 7692kb

input:

1000 1000 1000 0

output:

1000

result:

ok single line: '1000'

Test #63:

score: 0
Accepted
time: 1ms
memory: 7684kb

input:

1000 1500 1500 0

output:

1500

result:

ok single line: '1500'

Test #64:

score: 0
Accepted
time: 1ms
memory: 7820kb

input:

1000 2000 2000 0

output:

2000

result:

ok single line: '2000'

Test #65:

score: 0
Accepted
time: 1ms
memory: 7752kb

input:

1000 300 0 300

output:

600

result:

ok single line: '600'

Test #66:

score: 0
Accepted
time: 1ms
memory: 7820kb

input:

1000 500 0 500

output:

1000

result:

ok single line: '1000'

Test #67:

score: 0
Accepted
time: 1ms
memory: 7756kb

input:

1000 700 0 700

output:

1400

result:

ok single line: '1400'

Test #68:

score: 0
Accepted
time: 1ms
memory: 7752kb

input:

1000 1000 0 1000

output:

2000

result:

ok single line: '2000'

Test #69:

score: 0
Accepted
time: 1ms
memory: 7760kb

input:

1000 1500 0 1500

output:

2000

result:

ok single line: '2000'

Test #70:

score: 0
Accepted
time: 1ms
memory: 7744kb

input:

19 12 14 10

output:

24

result:

ok single line: '24'

Test #71:

score: 0
Accepted
time: 1ms
memory: 7636kb

input:

1000 2000 0 2000

output:

2000

result:

ok single line: '2000'

Test #72:

score: 0
Accepted
time: 0ms
memory: 7764kb

input:

1000 0 300 300

output:

600

result:

ok single line: '600'

Test #73:

score: 0
Accepted
time: 0ms
memory: 7772kb

input:

1000 0 500 500

output:

1000

result:

ok single line: '1000'

Test #74:

score: 0
Accepted
time: 1ms
memory: 7752kb

input:

1000 0 700 700

output:

1300

result:

ok single line: '1300'

Test #75:

score: 0
Accepted
time: 0ms
memory: 7768kb

input:

1000 0 1000 1000

output:

1000

result:

ok single line: '1000'

Test #76:

score: 0
Accepted
time: 1ms
memory: 7836kb

input:

1000 0 1500 1500

output:

1500

result:

ok single line: '1500'

Test #77:

score: 0
Accepted
time: 1ms
memory: 7816kb

input:

1000 0 2000 2000

output:

2000

result:

ok single line: '2000'

Test #78:

score: 0
Accepted
time: 1ms
memory: 7704kb

input:

2637 6773 9174 1735

output:

5274

result:

ok single line: '5274'

Test #79:

score: 0
Accepted
time: 1ms
memory: 7784kb

input:

2703 8304 3387 1641

output:

5406

result:

ok single line: '5406'

Test #80:

score: 0
Accepted
time: 1ms
memory: 7792kb

input:

6326 8700 3534 6848

output:

12652

result:

ok single line: '12652'

Test #81:

score: 0
Accepted
time: 1ms
memory: 7748kb

input:

15 15 12 17

output:

30

result:

ok single line: '30'

Test #82:

score: 0
Accepted
time: 1ms
memory: 7764kb

input:

2142 6609 4924 4096

output:

4284

result:

ok single line: '4284'

Test #83:

score: 0
Accepted
time: 1ms
memory: 7744kb

input:

9565 8872 6950 5722

output:

14594

result:

ok single line: '14594'

Test #84:

score: 0
Accepted
time: 1ms
memory: 7744kb

input:

547 2715 9932 9784

output:

1094

result:

ok single line: '1094'

Test #85:

score: 0
Accepted
time: 0ms
memory: 7628kb

input:

88 2600 8625 3878

output:

176

result:

ok single line: '176'

Test #86:

score: 0
Accepted
time: 1ms
memory: 7772kb

input:

1661 8169 2242 4146

output:

3322

result:

ok single line: '3322'

Test #87:

score: 0
Accepted
time: 1ms
memory: 7712kb

input:

4167 1089 8718 9606

output:

8334

result:

ok single line: '8334'

Test #88:

score: 0
Accepted
time: 1ms
memory: 7776kb

input:

4463 553 8538 5105

output:

5658

result:

ok single line: '5658'

Test #89:

score: 0
Accepted
time: 1ms
memory: 7748kb

input:

8142 9612 4922 8312

output:

16284

result:

ok single line: '16284'

Test #90:

score: 0
Accepted
time: 1ms
memory: 7804kb

input:

6612 6829 2173 4699

output:

11528

result:

ok single line: '11528'

Test #91:

score: 0
Accepted
time: 1ms
memory: 7832kb

input:

3435 7847 5234 2646

output:

6870

result:

ok single line: '6870'

Test #92:

score: 0
Accepted
time: 0ms
memory: 7748kb

input:

17 13 18 18

output:

31

result:

ok single line: '31'

Test #93:

score: 0
Accepted
time: 0ms
memory: 7768kb

input:

3425 9920 1367 7901

output:

6850

result:

ok single line: '6850'

Test #94:

score: 0
Accepted
time: 1ms
memory: 7904kb

input:

9741 9676 483 2051

output:

330597298

result:

ok single line: '330597298'

Test #95:

score: 0
Accepted
time: 1ms
memory: 7688kb

input:

2324 2737 5161 8088

output:

4648

result:

ok single line: '4648'

Test #96:

score: 0
Accepted
time: 0ms
memory: 7808kb

input:

6606 1493 824 9179

output:

11496

result:

ok single line: '11496'

Test #97:

score: 0
Accepted
time: 1ms
memory: 7812kb

input:

8265 9267 238 7595

output:

16530

result:

ok single line: '16530'

Test #98:

score: 0
Accepted
time: 0ms
memory: 7860kb

input:

6992 6132 164 5228

output:

11524

result:

ok single line: '11524'

Test #99:

score: 0
Accepted
time: 1ms
memory: 7712kb

input:

3647 6343 9074 4888

output:

7294

result:

ok single line: '7294'

Test #100:

score: 0
Accepted
time: 24ms
memory: 26960kb

input:

761933 965642 909762 628739

output:

1523866

result:

ok single line: '1523866'

Test #101:

score: 0
Accepted
time: 16ms
memory: 22944kb

input:

661992 436246 405301 690525

output:

1126771

result:

ok single line: '1126771'

Test #102:

score: 0
Accepted
time: 22ms
memory: 26072kb

input:

799120 245571 55209 777457

output:

1078237

result:

ok single line: '1078237'