QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#320249 | #8212. Football in Osijek | ucup-team1303# | WA | 2ms | 13972kb | C++20 | 1.7kb | 2024-02-03 14:51:21 | 2024-02-03 14:51:21 |
Judging History
answer
// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "[" << __LINE__ << "] "
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> inline void chkmax(T& x, T y) {x = max(x, y);}
template <typename T> inline void chkmin(T& x, T y) {x = min(x, y);}
template <typename T> inline void read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
x *= f;
}
const int N = 5e5 + 10;
int n, a[N], fa[N], sz[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
vector <int> t;
int rk[N], len[N];
int ans[N], g[N];
signed main() {
ms(ans, -1);
read(n);
F(i, 1, n) {
fa[i] = i;
// sz[i] = 1;
}
F(i, 1, n) {
read(a[i]);
// int t = a[i];
// while ()
fa[find(i)] = find(a[i]);
}
F(i, 1, n) sz[find(i)]++;
F(i, 1, n)
if (find(i) == i) {
t.push_back(sz[i]);
int cur = i, tot = 0;
// vector <int> h;
while (!rk[cur]) {
// h.push_back(cur);
rk[cur] = ++tot;
cur = a[cur];
}
len[i] = tot - rk[cur] + 1;
}
sort(all(t), greater <int> ());
int s = 0, w = 0;
F(i, 1, t.front()) ans[i] = 1;
for (int i: t) {
if (w) {
F(j, s + 1, s + i) ans[j] = w;
}
w++;
s += i;
}
F(i, 1, n)
if (find(i) == i) {
F(j, len[i], sz[i]) ans[j] = 0;
}
F(i, 1, n) cout << ans[i] << ' ';
return 0;
}
/* why?
*/
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 13972kb
input:
5 2 3 1 3 5
output:
0 1 0 0 1
result:
ok 5 number(s): "0 1 0 0 1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 13960kb
input:
1 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 2ms
memory: 13840kb
input:
2 2 2
output:
0 0
result:
ok 2 number(s): "0 0"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 13836kb
input:
10 4 7 2 8 4 3 4 9 7 3
output:
1 1 1 0 0 0 0 0 0 0
result:
wrong answer 8th numbers differ - expected: '1', found: '0'