题目地址:CF1100B Build a Contest
水题,比赛时没想就敲了个 \(O(n^2)\) 的暴力上去,结果过了Pretest,然后被Hack了
两个数组:
\(c_i\) 表示 \(i\) 出现过的次数
\(a_i\) 表示 \(i\) 在 \(c\) 中出现过的次数
初始时 \(a_0=n\) ,其他全为 \(0\)
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 100006;
int n, m, k, t, c[N], a[N];
int main() {
cin >> n >> m;
a[0] = n;
for (int i = 1; i <= m; i++) {
int x;
scanf("%d", &x);
--a[c[x]];
++a[++c[x]];
while (!a[t]) ++t;
if (t > k) {
putchar('1');
++k;
} else putchar('0');
}
return 0;
}