UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#203989#188. swaptkswls1006ms1388kbC++11965b2024-03-31 11:41:302024-03-31 13:10:30

answer

#include<bits/stdc++.h>
#define int long long
const int mod = 1000000007;
using namespace std;
int n, m, a[1005];
inline int solve(vector<int> v) {
	if (v.size() == 1 || v.size() == 0) return 1;
	vector<int> vl, vr;
	vl.clear(), vr.clear();
	int maxa = -1, maxb = 0;
	for (int i = 0; i < v.size(); i++) {
		if (v[i] > maxa) maxa = v[i], maxb = i;
	}
	int cnt = 0;
	for (int i = 0; i < maxb; i++) {
		if (v[i] + maxa <= m) cnt++;
		else vl.push_back(v[i]);
	}
	for (int i = maxb + 1; i < v.size(); i++) {
		if (v[i] + maxa <= m) cnt++;
		else vr.push_back(v[i]);
	}
	int ans = 1;
	for (int i = 1; i <= cnt; i++) {
		ans = ans * (vr.size() + vl.size() + i + 1) % mod;
	}
	ans = ans * solve(vl) % mod * solve(vr) % mod;
	return ans;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	vector<int> v;
	v.clear();
	for (int i = 1; i <= n; i++) cin >> a[i], v.push_back(a[i]);
	cout << solve(v);
}

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 0ms
memory: 1264kb

input:

5 1
1 5 2 3 4

output:

1

result:

ok single line: '1'

Test #2:

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

input:

5 4
5 1 3 2 4

output:

3

result:

ok single line: '3'

Test #3:

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

input:

5 615915903
542631646 683290875 948466698 37000543 333476514

output:

2

result:

ok single line: '2'

Test #4:

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

input:

5 679921638
98477774 80942367 274271684 449822600 166829910

output:

60

result:

ok single line: '60'

Subtask #2:

score: 30
Accepted

Test #5:

score: 30
Accepted
time: 1ms
memory: 1264kb

input:

7 334371207
163349301 375467315 896250414 270737361 167389825 122495138 515231792

output:

2

result:

ok single line: '2'

Test #6:

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

input:

8 49706300
357620994 228970663 352286819 276113041 658030654 494365242 526046486 846148572

output:

1

result:

ok single line: '1'

Test #7:

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

input:

9 724684064
245026615 650174461 126995527 668172353 187519608 539164759 367315342 30427970 421934090

output:

9

result:

ok single line: '9'

Test #8:

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

input:

9 14
9 3 1 8 5 7 6 2 4

output:

45360

result:

ok single line: '45360'

Test #9:

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

input:

9 2
8 1 7 5 6 9 2 3 4

output:

1

result:

ok single line: '1'

Test #10:

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

input:

10 18
1 7 8 3 5 6 2 4 10 9

output:

1814400

result:

ok single line: '1814400'

Test #11:

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

input:

10 5
9 2 8 1 7 10 3 6 5 4

output:

1

result:

ok single line: '1'

Test #12:

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

input:

10 282119946
159669259 629876439 166403567 504496676 356512828 595399143 676056596 139055672 2031388...

output:

1

result:

ok single line: '1'

Test #13:

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

input:

10 619860885
386687658 15287792 141318706 305225315 364074455 876041406 228804493 311308698 55187811...

output:

40

result:

ok single line: '40'

Subtask #3:

score: 50
Accepted

Test #14:

score: 50
Accepted
time: 0ms
memory: 1368kb

input:

998 72183673
336286907 556703903 48634023 5271611 667809688 278439146 78543510 217765937 435345700 3...

output:

12

result:

ok single line: '12'

Test #15:

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

input:

999 666874482
911681201 402717971 268709920 526148718 389928837 468048196 87541703 483599525 8493271...

output:

893213089

result:

ok single line: '893213089'

Test #16:

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

input:

999 447307519
605183435 881109162 342803620 913684102 574264658 526239529 860732879 181470304 935560...

output:

340242562

result:

ok single line: '340242562'

Test #17:

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

input:

999 1222
513 310 460 990 51 56 803 164 872 68 362 290 764 125 571 610 81 161 384 808 417 602 778 484...

output:

523159440

result:

ok single line: '523159440'

Test #18:

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

input:

999 1382
475 709 447 933 353 625 31 639 642 364 668 161 101 996 891 843 383 909 432 175 392 865 593 ...

output:

769957160

result:

ok single line: '769957160'

Test #19:

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

input:

1000 1030
639 31 780 236 798 198 727 921 172 784 71 686 39 255 961 785 886 83 923 344 375 627 270 21...

output:

339097646

result:

ok single line: '339097646'

Test #20:

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

input:

1000 1562
989 713 682 395 363 114 17 532 340 35 372 192 128 350 370 300 520 215 695 394 150 626 822 ...

output:

124222582

result:

ok single line: '124222582'

Test #21:

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

input:

1000 875728235
749707151 932043913 741974297 765153750 665107952 796739970 619268784 420100421 76459...

output:

103012568

result:

ok single line: '103012568'

Test #22:

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

input:

1000 712780623
82534622 791266815 494450552 553620962 703866045 566127834 971120771 391124667 972499...

output:

644291415

result:

ok single line: '644291415'