/home/toolbox/public_html/solutions/119/11991/a.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdint.h>
7 #include <math.h>
8 #include <stdlib.h>
9
10 #define TRUE (1 == 1)
11 #define FALSE (1 != 1)
12
13 #define DEBUG if (FALSE)
14
15 #define MAX_LINE 257
16
17 /*
18 * Author: Isaac Traxler
19 * Date: 2020-09-10
20 * Purpose: fun
21 * Problem: 11991
22 */
23
24 /*
25 * This template reads lines of data at a time until end of file.
26 */
27
28 /*
29 * 1 3 2 2 4 3 2 1
30 * - - - - - - -
31 * 1 1 8
32 * 2 3 7 index start last count
33 * 3 2 6
34 * 4 5 5
35 *
36 * next 9
37 *
38 * index 1 2 3 4 5 6 7 8
39 * next 8 6 4 7 0 0 0 0
40 */
41
42 #define MAX_ELEMENTS 100003
43 #define MAX_NUM 1000003
44 #define START 0
45 #define LAST 1
46 #define COUNT 2
47
48 int numElements;
49 int queries;
50 int ary[MAX_ELEMENTS];
51 int fat[MAX_ELEMENTS];
52 int tbl[MAX_NUM][3];
53 int fatNext;
54
55 void init()
56 {
57 /* FUNCTION init */
58 int i;
59
60 for (i=0; MAX_ELEMENTS>i; i++)
61 {
62 /* first parts */
63 tbl[i][START] = 0;
64 ary[i] = 0;
65 } /* first parts */
66 for (i=MAX_ELEMENTS ; MAX_NUM>i; i++)
67 {
68 /* rest of tbl */
69 tbl[i][START] = 0;
70 } /* rest of tbl */
71 fatNext = 1;
72 } /* FUNCTION init */
73
74 void dump()
75 {
76 /* FUNCTION dump */
77 int i;
78
79 printf("dump\n");
80 for (i=1; 10>=i; i++)
81 {
82 /* for each number */
83 printf("%d: %d %d %d\n", i, tbl[i][0], tbl[i][1], tbl[i][2]);
84 } /* for each number */
85
86 for (i=1; fatNext>=i; i++)
87 {
88 /* dump fat */
89 printf("%d: %d\n", i, fat[i]);
90 } /* dump fat */
91 } /* FUNCTION dump */
92
93 int getInput()
94 {
95 /* FUNCTION getInput */
96 int dataReadFlag;
97
98 dataReadFlag = (2 == scanf(" %d %d ", &numElements, &queries));
99 return (dataReadFlag);
100 } /* FUNCTION getInput */
101
102 void loadElements()
103 {
104 /* FUNCTION loadElements */
105 int i;
106 int tmp;
107
108 for (i=1; numElements >= i; i++)
109 {
110 /* for each element of the array */
111 scanf(" %d ", &tmp);
112 ary[i] = tmp;
113 if (0 == tbl[tmp][START])
114 {
115 /* first occurrence of ary[i] */
116 fat[fatNext] = 0;
117 tbl[tmp][START] = fatNext;
118 tbl[tmp][LAST] = fatNext;
119 tbl[tmp][COUNT] = 1;
120 fatNext++;
121 } /* first occurrence of ary[i] */
122 else
123 {
124 /* found a duplicate */
125 fat[fatNext] = 0;
126 fat[tbl[tmp][LAST]] = fatNext;
127 tbl[tmp][LAST] = fatNext;
128 tbl[tmp][COUNT] = tbl[tmp][COUNT] + 1;
129 fatNext++;
130 } /* found a duplicate */
131 } /* for each element of the array */
132
133 } /* FUNCTION loadElements */
134
135 void process()
136 {
137 /* FUNCTION process */
138 int q;
139 int occ;
140 int cnt;
141 int i;
142 int tmp;
143
144 loadElements();
145 DEBUG dump();
146 for (q=0; queries>q; q++)
147 {
148 /* for each query */
149 scanf(" %d %d ", &cnt, &occ);
150 if (0 == tbl[occ][START])
151 {
152 /* no elements that match this number */
153 printf("0\n");
154 } /* no elements that match this number */
155 else
156 {
157 /* at least one of them */
158 if (cnt > tbl[occ][COUNT])
159 {
160 /* not eough of this number */
161 printf("0\n");
162 } /* not eough of this number */
163 else
164 {
165 /* we have a winner */
166 if (1 == cnt)
167 {
168 /* we want first occurence */
169 printf("%d\n", tbl[occ][START]);
170 } /* we want first occurence */
171 else
172 {
173 /* not first */
174 if (tbl[occ][COUNT] == cnt)
175 {
176 /* we want the last */
177 printf("%d\n", tbl[occ][LAST]);
178 } /* we want the last */
179 else
180 {
181 /* one of the middle occurrences */
182 tmp = tbl[occ][START];
183 for (i=1; cnt > i; i++)
184 {
185 /* follow pointers */
186 tmp = fat[tmp];
187 } /* follow pointers */
188 printf("%d\n", tmp);
189 } /* one of the middle occurrences */
190 } /* not first */
191 } /* we have a winner */
192 } /* at least one of them */
193 } /* for each query */
194 } /* FUNCTION process */
195
196 int main()
197 {
198 /* main */
199 int moreToDo;
200
201 init();
202 moreToDo = getInput();
203 while (moreToDo)
204 {
205 /* while */
206 process();
207 init();
208 moreToDo = getInput();
209 } /* while */
210
211 return EXIT_SUCCESS;
212 } /* main */
213