oj.uz

Submission #519514

# Submission time Handle Problem Language Result Execution time Memory
519514 2022-01-26T13:14:57 Z amunduzbaev Space Pirate (JOI14_space_pirate) C++14
47 / 100
 1541 ms 148296 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;
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 436 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 316 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 436 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 316 KB Output is correct
15 Correct 233 ms 73464 KB Output is correct
16 Correct 212 ms 71248 KB Output is correct
17 Correct 226 ms 74076 KB Output is correct
18 Correct 1529 ms 146684 KB Output is correct
19 Correct 875 ms 116540 KB Output is correct
20 Correct 842 ms 123592 KB Output is correct
21 Correct 1453 ms 116752 KB Output is correct
22 Correct 760 ms 100548 KB Output is correct
23 Correct 1118 ms 113808 KB Output is correct
24 Correct 518 ms 95372 KB Output is correct
25 Correct 234 ms 72668 KB Output is correct
26 Correct 1541 ms 148296 KB Output is correct
27 Correct 637 ms 88996 KB Output is correct
28 Correct 762 ms 96344 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 440 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 436 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 316 KB Output is correct
15 Correct 233 ms 73464 KB Output is correct
16 Correct 212 ms 71248 KB Output is correct
17 Correct 226 ms 74076 KB Output is correct
18 Correct 1529 ms 146684 KB Output is correct
19 Correct 875 ms 116540 KB Output is correct
20 Correct 842 ms 123592 KB Output is correct
21 Correct 1453 ms 116752 KB Output is correct
22 Correct 760 ms 100548 KB Output is correct
23 Correct 1118 ms 113808 KB Output is correct
24 Correct 518 ms 95372 KB Output is correct
25 Correct 234 ms 72668 KB Output is correct
26 Correct 1541 ms 148296 KB Output is correct
27 Correct 637 ms 88996 KB Output is correct
28 Correct 762 ms 96344 KB Output is correct
29 Incorrect 8 ms 1592 KB Output isn't correct
30 Halted 0 ms 0 KB -