oj.uz

Submission #233698

# Submission time Handle Problem Language Result Execution time Memory
233698 2020-05-21T11:55:51 Z almogwald Space Pirate (JOI14_space_pirate) C++14
47 / 100
 1612 ms 524292 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define forr(i,a,b,c) for(int i=a;i<b;i+=c)
#define fort(i,a,b) forr(i,a,b,1)
#define forn(i,n) fort(i,1,n)
#define fori(i,n) fort(i,0,n)
#define forrb(i,a,b,c) for(int i=b-1;i>=a;i-=c)
#define fortb(i,a,b) forrb(i,a,b,1)
#define fornb(i,n) fortb(i,1,n)
#define forib(i,n) fortb(i,0,n)
using namespace std;
#define into(x) cin >> x;
typedef vector<int> veci;
typedef long long lol;
typedef pair<lol,lol> point;
#define def(x) lol x; into(x)

#define logn 60
int main() {
	ios::sync_with_stdio();
	def(n) def(m)
		veci a(n);
	vector<veci> x(n);
	vector<veci> y(n, veci(n,-1));
	vector<veci> f(logn, veci(n));
	fori(i, n) {
		into(a[i])
			a[i]--;
	}
	fori(i, n) {
		x[i].push_back(i);
		int cur = a[i];
		forn(j, n+1) {
			x[i].push_back(cur);
			if (y[i][cur] != -1) {
				break;
			}
			y[i][cur] = j;
			cur = a[cur];
		}
		f[0][i] = a[i];
	}
	forn(i, logn) {
		fori(j, n) {
			f[i][j] = f[i-1][f[i-1][j]];
		}
	}
	int norm = 0;
	lol mm = m;
	fori(k, logn) {
		if (mm % 2 == 1) {
			norm = f[k][norm];
		}
		mm /= 2;
	}
	veci b(n);
	fori(i, n) {
		lol mm = m - y[0][i] - 1;
		if (i == 0) {
			mm = m-1;
		}else if (y[0][i] == -1) {
			b[norm] += n;
			continue;
		}
		fori(j, n) {
			if (j == i) {
				b[i]++;
			} else 
			if (y[j][i] == -1) {
				int s =x[j].back();
				lol mmm = mm - y[j][s];
				int circle = x[s].size() - 2;
				b[x[s][(mmm+circle)% circle]]++;
			}else {
				b[x[j][mm % (y[j][i]+1)]]++;
			}
		}
	}
	fori(i, n) {
		cout << b[i] << endl;
	}
	return 0 ;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 460 KB Output is correct
15 Correct 65 ms 37760 KB Output is correct
16 Correct 33 ms 36600 KB Output is correct
17 Correct 79 ms 38048 KB Output is correct
18 Correct 1612 ms 80252 KB Output is correct
19 Correct 864 ms 60536 KB Output is correct
20 Correct 812 ms 65016 KB Output is correct
21 Correct 1341 ms 61432 KB Output is correct
22 Correct 543 ms 52344 KB Output is correct
23 Correct 1209 ms 60152 KB Output is correct
24 Correct 497 ms 49844 KB Output is correct
25 Correct 36 ms 37368 KB Output is correct
26 Correct 1452 ms 81144 KB Output is correct
27 Correct 456 ms 45944 KB Output is correct
28 Correct 514 ms 49656 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 293 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 460 KB Output is correct
15 Correct 65 ms 37760 KB Output is correct
16 Correct 33 ms 36600 KB Output is correct
17 Correct 79 ms 38048 KB Output is correct
18 Correct 1612 ms 80252 KB Output is correct
19 Correct 864 ms 60536 KB Output is correct
20 Correct 812 ms 65016 KB Output is correct
21 Correct 1341 ms 61432 KB Output is correct
22 Correct 543 ms 52344 KB Output is correct
23 Correct 1209 ms 60152 KB Output is correct
24 Correct 497 ms 49844 KB Output is correct
25 Correct 36 ms 37368 KB Output is correct
26 Correct 1452 ms 81144 KB Output is correct
27 Correct 456 ms 45944 KB Output is correct
28 Correct 514 ms 49656 KB Output is correct
29 Runtime error 293 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -