oj.uz

Submission #520093

# Submission time Handle Problem Language Result Execution time Memory
520093 2022-01-28T10:32:40 Z amunduzbaev Space Pirate (JOI14_space_pirate) C++14
80 / 100
 1486 ms 148292 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 225 ms 73412 KB Output is correct
16 Correct 209 ms 71252 KB Output is correct
17 Correct 235 ms 74072 KB Output is correct
18 Correct 1486 ms 146652 KB Output is correct
19 Correct 869 ms 116356 KB Output is correct
20 Correct 833 ms 123472 KB Output is correct
21 Correct 1459 ms 116752 KB Output is correct
22 Correct 746 ms 100548 KB Output is correct
23 Correct 1061 ms 113808 KB Output is correct
24 Correct 499 ms 95364 KB Output is correct
25 Correct 210 ms 72668 KB Output is correct
26 Correct 1393 ms 148292 KB Output is correct
27 Correct 602 ms 89000 KB Output is correct
28 Correct 703 ms 96344 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3660 KB Output is correct
2 Correct 29 ms 4664 KB Output is correct
3 Correct 21 ms 4284 KB Output is correct
4 Correct 17 ms 3512 KB Output is correct
5 Correct 29 ms 4672 KB Output is correct
6 Correct 21 ms 4280 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 225 ms 73412 KB Output is correct
16 Correct 209 ms 71252 KB Output is correct
17 Correct 235 ms 74072 KB Output is correct
18 Correct 1486 ms 146652 KB Output is correct
19 Correct 869 ms 116356 KB Output is correct
20 Correct 833 ms 123472 KB Output is correct
21 Correct 1459 ms 116752 KB Output is correct
22 Correct 746 ms 100548 KB Output is correct
23 Correct 1061 ms 113808 KB Output is correct
24 Correct 499 ms 95364 KB Output is correct
25 Correct 210 ms 72668 KB Output is correct
26 Correct 1393 ms 148292 KB Output is correct
27 Correct 602 ms 89000 KB Output is correct
28 Correct 703 ms 96344 KB Output is correct
29 Correct 13 ms 3660 KB Output is correct
30 Correct 29 ms 4664 KB Output is correct
31 Correct 21 ms 4284 KB Output is correct
32 Correct 17 ms 3512 KB Output is correct
33 Correct 29 ms 4672 KB Output is correct
34 Correct 21 ms 4280 KB Output is correct
35 Incorrect 14 ms 3640 KB Output isn't correct
36 Halted 0 ms 0 KB -