Submission #233697

#	Time	Username	Problem	Language	Result	Execution time	Memory
233697		almogwald	Space Pirate (JOI14_space_pirate)	C++14	10 / 100	2091 ms	524292 KiB

space_pirate

#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, veci(n+1));
	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][0]=i;
		int cur = a[i];
		forn(j, n+1) {
			x[i][j] = 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 ans = j;
				fori(k, logn) {
					if (mm&((lol)1<<k)) {
						ans = f[k][ans];
					}
				}
				b[ans]++;
			}else {
				b[x[j][mm % (y[j][i]+1)]]++;
			}
		}
	}
	fori(i, n) {
		cout << b[i] << endl;
	}
	return 0 ;
}

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