Submission #75753813

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
struct node_s {
  int value;
  struct node_s *prev, *next;
};
int pnext = 0;
struct node_s pool[512345];
struct node_s* get_node(void) {
  return &pool[pnext++];
}
int get_offset(int syuki) {
  int ans = 1, a = 10, b = 100;
  while (b > 0) {
    if (b & 1) ans = (int)((long long)ans * a % syuki);
    a = (int)((long long)a * a % syuki);
    b >>= 1;
  }
  return ans;
}
int N;
int A[512345];
int masu_log_cnt = 0;
int masu_log[512345];
int masu_pos[512345];
struct node_s* ans[512345];
struct node_s* calc(int node) {
  struct node_s *next_ans;
  if (ans[node]) return ans[node];
  if (masu_pos[node]) {
    struct node_s *first, *last, *ans_acc;
    int i;
    int offset;
    first = get_node();
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

struct node_s {
	int value;
	struct node_s *prev, *next;
};

int pnext = 0;
struct node_s pool[512345];

struct node_s* get_node(void) {
	return &pool[pnext++];
}

int get_offset(int syuki) {
	int ans = 1, a = 10, b = 100;
	while (b > 0) {
		if (b & 1) ans = (int)((long long)ans * a % syuki);
		a = (int)((long long)a * a % syuki);
		b >>= 1;
	}
	return ans;
}

int N;
int A[512345];

int masu_log_cnt = 0;
int masu_log[512345];
int masu_pos[512345];

struct node_s* ans[512345];

struct node_s* calc(int node) {
	struct node_s *next_ans;
	if (ans[node]) return ans[node];
	if (masu_pos[node]) {
		struct node_s *first, *last, *ans_acc;
		int i;
		int offset;
		first = get_node();
		first->value = node;
		last = first;
		for (i = masu_pos[node] + 1; i <= masu_log_cnt; i++) {
			struct node_s* new_node = get_node();
			new_node->value = masu_log[i];
			last->next = new_node;
			new_node->prev = last;
			last = new_node;
		}
		first->prev = last;
		last->next = first;
		offset = get_offset(masu_log_cnt - masu_pos[node] + 1);
		ans_acc = first;
		for (i = 0; i < offset; i++) ans_acc = ans_acc->next;
		return ans[node] = ans_acc;
	}
	masu_log[++masu_log_cnt] = node;
	masu_pos[node] = masu_log_cnt;
	next_ans = calc(A[node]);
	return ans[node] = next_ans->prev;
}

int main(void) {
	int i;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 1; i <= N; i++) {
		if (scanf("%d", &A[i]) != 1) return 1;
	}
	for (i = 1; i <= N; i++) {
		if (ans[i] == NULL) {
			masu_log_cnt = 0;
			calc(i);
		}
		printf(" %d" + (i == 1), ans[i]->value);
	}
	putchar('\n');
	return 0;
}

Submission Info

Judge Result