Submission #519514

#	Time	Username	Problem	Language	Result	Execution time	Memory
519514		amunduzbaev	Space Pirate (JOI14_space_pirate)	C++14	47 / 100	1541 ms	148296 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;
	}
}

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