QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#767201#6339. CookiesKiharaTouma0 2ms4224kbC++231.7kb2024-11-20 20:09:262024-11-20 20:09:26

Judging History

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

  • [2024-11-20 20:09:26]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:4224kb
  • [2024-11-20 20:09:26]
  • 提交

answer

//qoj6339
#include <bits/stdc++.h>
using namespace std;

const int N = 15010;
int n, m, a[N], b[N], c[N], pr[N], cnt[N], mx;
int f[N], fr[N];
pair<int, int> aa[N];

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i){
        scanf("%d", &a[i]);
        mx = max(mx, a[i]);
        aa[i] = make_pair(a[i], i);
        for(int j = 1; j <= a[i]; ++ j){
            ++ c[j];
        }
    }
    int tp = 0;
    for(int i = 1; i <= mx; ++ i){
        for(int j = 1; j <= c[i]; ++ j){
            pr[++tp] = i;
            cnt[tp] = j;
        }
    }
    scanf("%d", &m);
    for(int i = 1; i <= m; ++ i){
        scanf("%d", &b[i]);
    }
    sort(aa + 1, aa + n + 1);
    reverse(aa + 1, aa + n + 1);
    sort(b + 1, b + m + 1);
    reverse(b + 1, b + m + 1);
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    cnt[0] = 1e9;
    for(int i = 1; i <= tp; ++ i){
        for(int j = 1; j <= m; ++ j){
            if(i >= b[j]){
                if(pr[i] == pr[i-b[j]+1]){
                    f[i] = min(f[i], f[i-b[j]] + 1);
                    if(f[i] == f[i-b[j]] + 1){
                        fr[i] = i - b[j];
                    }
                } else if(pr[i] == pr[i-b[j]+1] + 1 && cnt[i] < cnt[i-b[j]+1]){
                    f[i] = min(f[i], f[i-b[j]] + 1);
                    if(f[i] == f[i-b[j]] + 1){
                        fr[i] = i - b[j];
                    }
                }
            }
        }
    }
    printf("%d\n", f[tp]);
    int x = tp;
    for(int i = 1; i <= f[tp]; ++ i){
        printf("%d ", x - fr[x]);
        for(int j = fr[x] + 1; j <= x; ++ j){
            printf("%d ", aa[cnt[j]].second);
        }
        puts("");
        x = fr[x];
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

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

input:

1
1
1
1

output:

1
1 1 

result:

ok good!

Test #2:

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

input:

2
1 1
1
1

output:

2
1 1 
1 2 

result:

ok good!

Test #3:

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

input:

2
1 1
1
2

output:

1
2 2 1 

result:

ok good!

Test #4:

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

input:

2
1 1
2
1 2

output:

1
2 2 1 

result:

ok good!

Test #5:

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

input:

4
1 1 1 1
2
2 3

output:

2
2 2 1 
2 4 3 

result:

ok good!

Test #6:

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

input:

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

output:

2
4 4 3 2 1 
4 8 7 6 5 

result:

ok good!

Test #7:

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

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 1 
1 2 
1 3 
1 4 
1 5 
1 6 
1 7 
1 8 
1 9 
1 10 
1 11 
1 12 
1 13 
1 14 
1 15 
1 16 
1 17 
1 18 
1 19 
1 20 
1 21 
1 22 
1 23 
1 24 
1 25 
1 26 
1 27 
1 28 
1 29 
1 30 
1 31 
1 32 
1 33 
1 34 
1 35 
1 36 
1 37 
1 38 
1 39 
1 40 
1 41 
1 42 
1 43 
1 44 
1 45 
1 46 
1 47 
1 48 
1 49 
1 50 
1 51 ...

result:

ok good!

Test #8:

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

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: 6
Accepted
time: 1ms
memory: 3836kb

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
1 1 
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 4...

result:

ok good!

Test #10:

score: 0
Time Limit Exceeded

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:

1061109567
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 4...

result:


Subtask #2:

score: 0
Time Limit Exceeded

Test #28:

score: 7
Accepted
time: 1ms
memory: 3828kb

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: 7
Accepted
time: 0ms
memory: 3940kb

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: 7
Accepted
time: 1ms
memory: 4040kb

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: 7
Accepted
time: 2ms
memory: 4224kb

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: 7
Accepted
time: 0ms
memory: 4004kb

input:

2
2 1
1
1

output:

3
1 1 
1 2 
1 1 

result:

ok good!

Test #33:

score: 0
Time Limit Exceeded

input:

2
1 2
1
2

output:

1061109567
3 2 1 2 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0...

result:


Subtask #3:

score: 0
Time Limit Exceeded

Test #45:

score: 12
Accepted
time: 1ms
memory: 3860kb

input:

2
7 8
2
1 2

output:

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

result:

ok good!

Test #46:

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

input:

3
5 4 6
2
2 3

output:

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

result:

ok good!

Test #47:

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

input:

3
4 2 9
3
1 2 3

output:

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

result:

ok good!

Test #48:

score: 0
Time Limit Exceeded

input:

4
3 5 4 3
2
3 4

output:

1061109567
15 2 3 4 1 2 3 4 1 2 3 4 1 2 3 2 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
0 
...

result:


Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%