This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <cstring>
#include <vector>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 3e3 + 50;
const int M = 1e5 + 500;
const int LOG = 62;
int dis[N][N], udem[N], kor[N][N];
int bio[N], cnt[N], P[N], klsk, cik[N];
vector < int > red;
int n;
ll k, fin[M];
void precompute(int x){
memset(bio, 0, sizeof(bio));
int cur = x, cdis = 0;
while(!bio[cur]){
kor[x][cdis] = cur;
bio[cur] = 1;
dis[x][cur] = cdis++;
cur = P[cur];
}
udem[x] = cur;
if(cur == x)
cik[x] = cdis;
}
int siz = 0;
int get(int a, int b){
if(a == b)
return a;
int nw = (a - b + siz) % siz + 1;
int koji = (k - a) % nw;
if(koji == 0)
return a;
return (b + koji - 1) % siz;
}
int main(){
memset(dis, -1, sizeof(dis));
scanf("%d%lld", &n, &k);
for(int i = 1;i <= n;i++)
scanf("%d", P + i);
if(n > 3000){
int cur = 1;
while(!bio[cur]){
red.PB(cur);
bio[cur] = 1;
cur = P[cur];
siz++;
}
fin[red[k % siz]] += (ll)(n - siz) * n;
for(int dif = - siz - 1;dif <= siz - 1;dif++){
int a = -dif, b = 0;
if(dif >= 0)
a = 0, b = dif;
for(;a < siz && b < siz;){
int cur = get(a, b), kor = 0;
for(int k = 17;k >= 0;k--){
if(a + kor + (1 << k) >= siz || b + kor + (1 << k) >= siz)
continue;
if(get(a + kor + (1 << k), b + kor + (1 << k)) == cur)
kor += (1 << k);
}
fin[red[cur]] += kor + 1;
a += kor + 1; b += kor + 1;
}
}
for(int i = 1;i <= n;i++){
if(!bio[i])
printf("%d\n", siz);
else
printf("%lld\n", fin[i]);
}
return 0;
}
for(int i = 1;i <= n;i++)
precompute(i);
int koji_kl = (k - dis[1][udem[1]]) % cik[udem[1]];
klsk = kor[udem[1]][koji_kl];
for(int a = 1;a <= n;a++){
for(int b = 1;b <= n;b++){
int ans = 0;
if(dis[1][a] == -1){
ans = klsk;
}
else if(dis[b][a] != -1){
int koji = (k - dis[1][a]) % (dis[b][a] + 1);
if(koji == 0)
ans = a;
else
ans = kor[b][koji - 1];
}
else{
int koji = (k - dis[1][a] - 1 - dis[b][udem[b]]) % cik[udem[b]];
ans = kor[udem[b]][koji];
}
cnt[ans]++;
}
}
for(int i = 1;i <= n;i++)
printf("%d\n", cnt[i]);
return 0;
}
Compilation message (stderr)
space_pirate.cpp: In function 'int main()':
space_pirate.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
53 | scanf("%d%lld", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~
space_pirate.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
55 | scanf("%d", P + i);
| ~~~~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |