CQUPT OJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#16831 #1062. 美丽MEX Wrong Answer 80 163 ms 3488 K C++ / 981 B C192023212364 2024-03-16 17:49:37
显示原始代码 
#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 1e5 + 10;
int n, a[N];
bool cmp(int x, int y) { return x < y; }
int ans, tot[N];
int zh(int x) {
    int f[x + 10], l = 1, r = 0, q[x];
    for (int i = 0; i <= x; i++) f[x] = 0;
    f[0] = tot[0] - 1;
    for (int i = 1; i <= x; i++) {
        f[i] = (tot[0] - 1) * (i + 1);
        if (l > r or tot[q[r]] > tot[i]) {
            r++;
            q[r] = i;
        }
        for (int j = l; j <= r; j++) f[i] = min(f[i], f[q[j] - 1] + (tot[q[j]] - 1) * (i + 1) + q[j]);
    }
    return f[x];
}
void A() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    sort(a + 1, a + n + 1, cmp);
    if (a[1] > 0) {
        printf("0\n");
        return;
    }
    if (a[n] == 0) {
        printf("%lld\n", n - 1);
        return;
    }
    ans = 0;
    int sl = 1;
    for (int i = 0; a[sl] == i; i++) {
        tot[i] = 0;
        while (a[sl] == i and sl <= n) {
            tot[i]++;
            sl++;
        }
        if (a[sl] != i + 1 or sl > n) {
            printf("%lld\n", zh(i));
            return;
        }
    }
}
signed main() {
    int t;
    scanf("%lld", &t);
    while (t--) A();
    return 0;
}
子任务 #1
Wrong Answer
得分：80
测试点 #1
Accepted
得分：100
用时：29 ms
内存：476 KiB

输入文件（1.in） 

74342
12128
650398022 79352152 952526941 79743757 135929947 400939848 528979602 289819240 91987887
<1378918 bytes omitted>

答案文件（1.out） 

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
<222926 bytes omitted>

用户输出 

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

<148556 bytes omitted>

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：21 ms
内存：3488 KiB

输入文件（2.in） 

1
100000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 
<588802 bytes omitted>

答案文件（2.out） 

0

用户输出 

0

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：16 ms
内存：1180 KiB

输入文件（3.in） 

1
100000
91939 38242 27047 12867 13573 10622 12021 7516 10101 2214 6872 4723 3920 4734 5061 2943 5
<205476 bytes omitted>

答案文件（3.out） 

172092

用户输出 

172092

系统信息 

Exited with return code 0
测试点 #4
Accepted
得分：100
用时：15 ms
内存：688 KiB

输入文件（4.in） 

100
100
1 1 2 4 0 1 4 3 4 2 4 2 0 0 3 4 1 1 3 1 4 2 4 2 3 4 0 1 1 3 1 3 4 0 1 1 1 4 4 1 0 0 1 2 1 
<200502 bytes omitted>

答案文件（4.out） 

80
155
655
755
535
10
585
1000
825
835
820
227
665
440
970
295
470
140
830
1005

<398 bytes omitted>

用户输出 

80
155
655
755
535
10
585
1000
825
835
820
227
665
440
970
295
470
140
830
1005
260
220
875
460
920
45
475
680
200
850
35
160
58
<270 bytes omitted>

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：15 ms
内存：888 KiB

输入文件（5.in） 

10
490
3 3 2 1 2 1 0 4 1 4 4 4 0 3 3 3 3 4 0 0 0 0 2 0 2 3 4 2 3 4 2 1 0 4 2 1 1 2 4 1 2 4 2 2 4 2
<199973 bytes omitted>

答案文件（5.out） 

480
725
1705
1835
8060
3970
9000
4995
5570
64035

用户输出 

480
725
1705
1835
8060
3970
9000
4995
5570
64035

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：16 ms
内存：1196 KiB

输入文件（6.in） 

1
100000
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
<383949 bytes omitted>

答案文件（6.out） 

1708

用户输出 

1708

系统信息 

Exited with return code 0
测试点 #7
Accepted
得分：100
用时：14 ms
内存：1164 KiB

输入文件（7.in） 

1
100000
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
<199912 bytes omitted>

答案文件（7.out） 

99999

用户输出 

99999

系统信息 

Exited with return code 0
测试点 #8
Wrong Answer
得分：0
用时：14 ms
内存：420 KiB

输入文件（8.in） 

236
139
65 43 28 34 20 3 8 14 14 7 10 3 5 7 6 2 3 5 4 1 5 3 0 1 1 2 2 1 3 3 4 3 2 3 2 3 0 0 0 1 3 
<206602 bytes omitted>

答案文件（8.out） 

173
125
159
833
363
760
1177
285
872
435
866
1379
168
691
542
1105
652
1527
1214

<1072 bytes omitted>

用户输出 

173
125
159
833
363
760
1177
285
872
435
866
1379
168
691
542
1105
652
1527
1214
1521
594
1295
1251
379
1416
954
1291
3
423
834

<808 bytes omitted>

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #9
Accepted
得分：100
用时：18 ms
内存：2244 KiB

输入文件（9.in） 

1
100000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 
<388801 bytes omitted>

答案文件（9.out） 

50001

用户输出 

50001

系统信息 

Exited with return code 0
测试点 #10
Wrong Answer
得分：0
用时：5 ms
内存：320 KiB

输入文件（10.in） 

1000
547
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 
<282301 bytes omitted>

答案文件（10.out） 

274
0
0
0
0
0
0
0
0
48
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
<2922 bytes omitted>

用户输出 

274
-1
0
0
0
0
0
0
0
48
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
<2837 bytes omitted>

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
CQUPT OJ Powered by SYZOJ.