Submission #520093

#	Time	Username	Problem	Language	Result	Execution time	Memory
520093		amunduzbaev	Space Pirate (JOI14_space_pirate)	C++14	80 / 100	1486 ms	148292 KiB

space_pirate

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define int long long
 
void solve(int n, int k, vector<int>& p){
	vector<vector<int>> pp(n);
	vector<vector<int>> d(n, vector<int>(n, 2e18));
	for(int i=0;i<n;i++){
		d[i][i] = 0, pp[i].push_back(i);
		while(d[i][p[pp[i].back()]] == 2e18){
			d[i][p[pp[i].back()]] = d[i][pp[i].back()] + 1;
			pp[i].push_back(p[pp[i].back()]);
		}
	}
	
	auto last = [&](int x) { return pp[x].back(); };
	auto loop = [&](int x) { return p[last(x)]; };
	
	vector<int> sz(n);
	for(int i=0;i<n;i++){
		sz[i] = d[i][last(i)] - d[i][loop(i)] + 1;
	}
	
	auto find = [&](int a, int b){
		if(b < (int)pp[a].size()){
			return pp[a][b];
		}
		int cnt = (b - (int)pp[a].size()) % sz[a];
		return pp[a][d[a][loop(a)] + cnt];
	};
	
	vector<int> res(n);
	for(int a=0;a<n;a++){
		for(int b=0;b<n;b++){
			if(d[0][a] > k){
				res[find(0, k)]++;
			} else {
				if(d[b][a] > k){
					res[find(b, k - d[0][a] - 1)]++;
				} else {
					int r = (k - d[0][a] - 1) % (d[b][a] + 1);
					res[find(b, r)]++;
				}
			}
		}
	}
	
	for(int i=0;i<n;i++) cout<<res[i]<<"\n";
}
 
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	//~ freopen("tmp.txt", "r", stdin);
	int n; long long k; cin>>n>>k;
	vector<int> p(n);
	for(int i=0;i<n;i++) cin>>p[i], p[i]--;
	
	if(n <= 3000){
		solve(n, k, p);
		return 0;
	}
	
	vector<int> ss, used(n);
	int u=0;
	while(!used[u]){
		ss.push_back(u);
		used[u] = 1;
		u = p[u];
	}
	
	vector<int> res(n);
	int sz = (int)ss.size();
	res[ss[k % sz]] += (n - sz) * n + sz;
	for(int i=0;i<n;i++){
		if(!used[i]) res[i] += sz;
	}
	
	for(int i=0;i<sz;i++){
		res[ss[i]]++;
	}
	
	for(int l=2;l<sz;l++){
		res[ss[k % l]] += l - 1 - (k % l);
		res[ss[sz - l + k % l]] += k % l;
	} 
	
	for(int l=2;l<sz;l++){
		for(int p=k%l;p<sz;p+=l){
			int lx = max(p, l - 1), rx = min(sz - 1, p + l - 1);
			res[ss[p]] += rx - lx + 1;
		}
	}
	
	for(int i=0;i<n;i++){
		cout<<res[i]<<"\n";
	}
}

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