QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#241486#6339. CookiesLeasier12 9ms58856kbC++982.0kb2023-11-06 08:43:562023-11-06 08:43:56

Judging History

你现在查看的是最新测评结果

  • [2023-11-06 08:43:56]
  • 评测
  • 测评结果:12
  • 用时:9ms
  • 内存:58856kb
  • [2023-11-06 08:43:56]
  • 提交

answer

#include <iostream>
#include <queue>
#include <vector>
#include <bitset>

using namespace std;

int a[15007], suf[15007], val[15007], b[15007], ansc[15007];
pair<int, int> save[15007];
priority_queue<pair<int, int> > q;
bitset<15007> temp, bs[15007];
vector<bitset<15007> > v[15007];

int main(){
	int n, max_val = 0, sum = 0, m, ansx = -1;
	cin >> n;
	for (register int i = 1; i <= n; i++){
		cin >> a[i];
		suf[a[i]]++;
		max_val = max(max_val, a[i]);
		sum += a[i];
	}
	for (register int i = max_val; i >= 1; i--){
		suf[i] += suf[i + 1];
	}
	for (register int i = 1; i <= max_val; i++){
		val[i] = val[i - 1] + suf[i];
	}
	for (register int i = max_val + 1; i <= sum; i++){
		val[i] = sum;
	}
	bs[0][0] = true;
	for (register int i = 1; i <= sum; i++){
		bs[i] = bs[i - 1];
		for (register int j = val[i - 1] + 1; j <= val[i]; j++){
			bs[i][j] = true;
		}
	}
	cin >> m;
	for (register int i = 1; i <= m; i++){
		cin >> b[i];
	}
	v[m + 1].resize(1);
	v[m + 1][0][0] = true;
	for (register int i = m; i >= 1; i--){
		int size = v[i + 1].size();
		v[i].resize(sum / b[i] + 1);
		for (register int j = 0; b[i] * j <= sum; j++){
			if (j < size) v[i][j] = v[i + 1][j];
			if (j > 0){
				temp = v[i][j - 1];
				temp <<= b[i];
				v[i][j] |= temp;
			}
			v[i][j] &= bs[j];
		}
	}
	for (register int i = 0; i <= sum; i++){
		if (v[1][i][sum]){
			ansx = i;
			break;
		}
	}
	if (ansx == -1){
		cout << -1;
		return 0;
	}
	cout << ansx << endl;
	for (register int i = ansx, j = sum, k = 1; i >= 1; i--, j -= b[k]){
		while (!v[k][i][j] || !v[k][i - 1][j - b[k]]) k++;
		ansc[i] = b[k];
	}
	for (register int i = 1; i <= n; i++){
		q.push(make_pair(a[i], i));
	}
	for (register int i = 1; i <= ansx; i++){
		cout << ansc[i] << " ";
		for (register int j = 1; j <= ansc[i]; j++){
			save[j] = q.top();
			q.pop();
			cout << save[j].second << " ";
		}
		cout << endl;
		for (register int j = 1; j <= ansc[i]; j++){
			if (--save[j].first > 0) q.push(save[j]);
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 6
Accepted
time: 0ms
memory: 31684kb

input:

1
1
1
1

output:

1
1 1 

result:

ok good!

Test #2:

score: 0
Accepted
time: 6ms
memory: 31608kb

input:

2
1 1
1
1

output:

2
1 2 
1 1 

result:

ok good!

Test #3:

score: 0
Accepted
time: 6ms
memory: 31424kb

input:

2
1 1
1
2

output:

1
2 2 1 

result:

ok good!

Test #4:

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

input:

2
1 1
2
1 2

output:

1
2 2 1 

result:

ok good!

Test #5:

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

input:

4
1 1 1 1
2
2 3

output:

2
2 4 3 
2 2 1 

result:

ok good!

Test #6:

score: 0
Accepted
time: 6ms
memory: 31448kb

input:

8
1 1 1 1 1 1 1 1
3
1 4 5

output:

2
4 8 7 6 5 
4 4 3 2 1 

result:

ok good!

Test #7:

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

input:

500
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

500
1 500 
1 499 
1 498 
1 497 
1 496 
1 495 
1 494 
1 493 
1 492 
1 491 
1 490 
1 489 
1 488 
1 487 
1 486 
1 485 
1 484 
1 483 
1 482 
1 481 
1 480 
1 479 
1 478 
1 477 
1 476 
1 475 
1 474 
1 473 
1 472 
1 471 
1 470 
1 469 
1 468 
1 467 
1 466 
1 465 
1 464 
1 463 
1 462 
1 461 
1 460 
1 459 
1 ...

result:

ok good!

Test #8:

score: 0
Accepted
time: 6ms
memory: 31432kb

input:

500
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

1
500 500 499 498 497 496 495 494 493 492 491 490 489 488 487 486 485 484 483 482 481 480 479 478 477 476 475 474 473 472 471 470 469 468 467 466 465 464 463 462 461 460 459 458 457 456 455 454 453 452 451 450 449 448 447 446 445 444 443 442 441 440 439 438 437 436 435 434 433 432 431 430 429 428 42...

result:

ok good!

Test #9:

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

input:

500
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

2
499 500 499 498 497 496 495 494 493 492 491 490 489 488 487 486 485 484 483 482 481 480 479 478 477 476 475 474 473 472 471 470 469 468 467 466 465 464 463 462 461 460 459 458 457 456 455 454 453 452 451 450 449 448 447 446 445 444 443 442 441 440 439 438 437 436 435 434 433 432 431 430 429 428 42...

result:

ok good!

Test #10:

score: -6
Runtime Error

input:

500
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:


result:


Subtask #2:

score: 0
Runtime Error

Test #28:

score: 7
Accepted
time: 3ms
memory: 31476kb

input:

1
15
1
1

output:

15
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 

result:

ok good!

Test #29:

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

input:

1
500
1
1

output:

500
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1...

result:

ok good!

Test #30:

score: 0
Accepted
time: 9ms
memory: 36676kb

input:

1
3000
1
1

output:

3000
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
...

result:

ok good!

Test #31:

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

input:

1
15000
1
1

output:

15000
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 
1 1 ...

result:

ok good!

Test #32:

score: 0
Accepted
time: 3ms
memory: 31440kb

input:

2
2 1
1
1

output:

3
1 1 
1 2 
1 1 

result:

ok good!

Test #33:

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

input:

2
1 2
1
2

output:

-1

result:

ok no solution

Test #34:

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

input:

3
1 2 3
1
2

output:

3
2 3 2 
2 3 2 
2 3 1 

result:

ok good!

Test #35:

score: -7
Runtime Error

input:

3
3 2 1
1
3

output:

3

result:


Subtask #3:

score: 12
Accepted

Test #45:

score: 12
Accepted
time: 0ms
memory: 31532kb

input:

2
7 8
2
1 2

output:

8
2 2 1 
2 2 1 
2 2 1 
2 2 1 
2 2 1 
2 2 1 
2 2 1 
1 2 

result:

ok good!

Test #46:

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

input:

3
5 4 6
2
2 3

output:

6
3 3 1 2 
3 3 1 2 
3 3 1 2 
2 3 1 
2 3 2 
2 3 1 

result:

ok good!

Test #47:

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

input:

3
4 2 9
3
1 2 3

output:

9
3 3 1 2 
3 3 1 2 
2 3 1 
2 3 1 
1 3 
1 3 
1 3 
1 3 
1 3 

result:

ok good!

Test #48:

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

input:

4
3 5 4 3
2
3 4

output:

5
3 2 3 4 
3 2 3 1 
3 2 4 3 
3 2 1 4 
3 3 2 1 

result:

ok good!

Test #49:

score: 0
Accepted
time: 3ms
memory: 31560kb

input:

4
1 4 5 5
3
1 3 4

output:

5
3 4 3 2 
3 4 3 2 
3 4 3 2 
3 4 3 2 
3 4 3 1 

result:

ok good!

Test #50:

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

input:

4
3 3 6 3
3
2 3 4

output:

6
4 3 4 2 1 
3 3 4 2 
2 3 1 
2 3 4 
2 3 2 
2 3 1 

result:

ok good!

Test #51:

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

input:

5
4 3 3 3 1
3
2 4 5

output:

4
4 1 4 3 2 
4 1 4 3 2 
4 1 5 4 3 
2 2 1 

result:

ok good!

Test #52:

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

input:

5
4 3 3 3 2
3
3 4 5

output:

4
5 1 4 3 2 5 
4 1 4 3 2 
3 1 5 4 
3 3 2 1 

result:

ok good!

Test #53:

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

input:

5
4 4 4 2 1
3
2 4 5

output:

5
5 3 2 1 4 5 
4 3 2 1 4 
2 3 2 
2 1 3 
2 2 1 

result:

ok good!

Test #54:

score: 0
Accepted
time: 3ms
memory: 31472kb

input:

5
3 3 3 3 3
3
1 2 4

output:

5
4 5 4 3 2 
4 1 5 4 3 
4 2 1 5 4 
2 3 2 
1 1 

result:

ok good!

Test #55:

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

input:

6
3 3 3 2 2 2
3
2 4 6

output:

-1

result:

ok no solution

Test #56:

score: 0
Accepted
time: 3ms
memory: 31512kb

input:

6
3 3 3 2 2 2
3
2 5 6

output:

3
5 3 2 1 6 5 
5 4 3 2 1 6 
5 5 4 3 2 1 

result:

ok good!

Test #57:

score: 0
Accepted
time: 3ms
memory: 31584kb

input:

6
4 4 3 2 1 1
3
1 3 5

output:

5
5 2 1 3 4 6 
5 2 1 3 5 4 
3 2 1 3 
1 2 
1 1 

result:

ok good!

Test #58:

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

input:

6
7 2 2 2 1 1
5
2 3 4 5 6

output:

7
3 1 4 3 
2 1 2 
2 1 6 
2 1 5 
2 1 4 
2 1 3 
2 2 1 

result:

ok good!

Test #59:

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

input:

7
3 3 3 2 2 1 1
3
1 4 6

output:

4
6 3 2 1 5 4 7 
4 3 2 1 6 
4 5 4 3 2 
1 1 

result:

ok good!

Test #60:

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

input:

7
4 4 3 1 1 1 1
3
1 4 6

output:

6
4 2 1 3 7 
4 2 1 3 6 
4 2 1 5 4 
1 3 
1 2 
1 1 

result:

ok good!

Test #61:

score: 0
Accepted
time: 5ms
memory: 31464kb

input:

8
2 2 2 2 2 2 2 1
6
1 2 3 4 6 7

output:

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

result:

ok good!

Test #62:

score: 0
Accepted
time: 3ms
memory: 31440kb

input:

8
3 3 3 2 1 1 1 1
4
4 6 7 8

output:

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

result:

ok good!

Test #63:

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

input:

8
4 3 3 1 1 1 1 1
4
1 6 7 8

output:

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

result:

ok good!

Test #64:

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

input:

9
4 3 2 1 1 1 1 1 1
4
3 4 5 7

output:

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

result:

ok good!

Test #65:

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

input:

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

output:

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

result:

ok good!

Test #66:

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

input:

14
2 1 1 1 1 1 1 1 1 1 1 1 1 1
14
1 2 3 4 5 6 7 8 9 10 11 12 13 14

output:

2
14 1 14 13 12 11 10 9 8 7 6 5 4 3 2 
1 1 

result:

ok good!

Test #67:

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

input:

4
2 2 2 1
2
1 4

output:

4
4 3 2 1 4 
1 3 
1 2 
1 1 

result:

ok good!

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%