Submission #295581

#	Time	Username	Problem	Language	Result	Execution time	Memory
295581		patrikpavic2	Space Pirate (JOI14_space_pirate)	C++17	80 / 100	1134 ms	73080 KiB

space_pirate

#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[M], cnt[N], P[M], 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);
      |   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 37 / 37
• Subtask 3: 33 / 33
• Subtask 4: 0 / 20