青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

雪竹的天空

theorix

  C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
  34 隨筆 :: 0 文章 :: 20 評論 :: 0 Trackbacks
Robotic Sort

Time limit: 2 Seconds   Memory limit: 32768K  
Total Submit: 12   Accepted Submit: 4  

Somewhere deep in the Czech Technical University buildings, there are laboratories for examining mechanical and electrical properties of various materials. In one of yesterday's presentations, you have seen how was one of the laboratories changed into a new multimedia lab. But there are still others, serving to their original purposes.

In this task, you are to write software for a robot that handles samples in such a laboratory. Imagine there are material samples lined up on a running belt. The samples have different heights, which may cause troubles to the next processing unit. To eliminate such troubles, we need to sort the samples by their height into the ascending order.

Reordering is done by a mechanical robot arm, which is able to pick up any number of consecutive samples and turn them round, such that their mutual order is reversed. In other words, one robot operation can reverse the order of samples on positions between A and B.

A possible way to sort the samples is to find the position of the smallest one (P1) and reverse the order between positions 1 and P1, which causes the smallest sample to become first. Then we find the second one on position P2 and reverse the order between 2 and P2. Then the third sample is located etc.

 

 

The picture shows a simple example of 6 samples. The smallest one is on the 4th position, therefore, the robot arm reverses the first 4 samples. The second smallest sample is the last one, so the next robot operation will reverse the order of five samples on positions 2 - 6. The third step will be to reverse the samples 3 - 4 etc.

Your task is to find the correct sequence of reversal operations that will sort the samples using the above algorithm. If there are more samples with the same height, their mutual order must be preserved: the one that was given first in the initial order must be placed before the others in the final order too.

Input

The input consists of several scenarios. Each scenario is described by two lines. The first line contains one integer number N, the number of samples, 1 <= N <= 100 000. The second line lists exactly N space-separated positive integers, they specify the heights of individual samples and their initial order.

The last scenario is followed by a line containing zero.

Output

For each scenario, output one line with exactly N integers P1, P2, . . .PN, separated by a space. Each Pi must be an integer (1 <= Pi <= N) giving the position of the i-th sample just before the i-th reversal operation.

Note that if a sample is already on its correct position Pi, you should output the number Pi anyway, indicating that the "interval between Pi and Pi" (a single sample) should be reversed.

Sample Input

6
3 4 5 1 6 2
4
3 3 2 1
0

Sample Output

4 6 4 5 6 6
4 2 4 4

 


Problem Source: The 2007 ACM Central Europe Programming Contest

 

 


  1/*
  2* Sample solution to the Sort problem.
  3* Central Europe Regional Contest 2007.
  4*
  5* Zdenek Dvorak, 2007
  6*/

  7
  8#include <stdio.h>
  9#include <stdlib.h>
 10
 11#define MAXN 200000
 12static int n, input[MAXN], ipermut[MAXN], permut[MAXN];
 13
 14struct node
 15{
 16int reverse, size, present;
 17struct node *l, *r, *f;
 18}
;
 19
 20static struct node path_nodes[MAXN];
 21static void
 22dump_tree (struct node *t, int reverse)
 23{
 24struct node *l, *r;
 25
 26reverse ^= t->reverse;
 27
 28= reverse ? t->r : t->l;
 29= reverse ? t->l : t->r;
 30
 31if (l)
 32    dump_tree (l, reverse);
 33
 34if (t->present)
 35    printf ("%d ", (int) (t - path_nodes));
 36
 37if (r)
 38    dump_tree (r, reverse);
 39}

 40
 41static void
 42dump_path (void)
 43{
 44int i;
 45
 46printf ("\n");
 47for (i = 0; i < n; i++)
 48    if (!path_nodes[i].f)
 49      {
 50printf ("--- ");
 51dump_tree (&path_nodes[i], 0);
 52      }

 53
 54printf (" ---\n");
 55}

 56
 57static void
 58clean_reverse (struct node *tree)
 59{
 60struct node *t;
 61
 62if (!tree->reverse)
 63    return;
 64
 65= tree->l; tree->= tree->r; tree->= t;
 66if (tree->l)
 67    tree->l->reverse = !tree->l->reverse;
 68if (tree->r)
 69    tree->r->reverse = !tree->r->reverse;
 70tree->reverse = 0;
 71}

 72
 73static void
 74fix_size (struct node *t)
 75{
 76int lsize = t->? t->l->size : 0;
 77int rsize = t->? t->r->size : 0;
 78
 79t->size = lsize + rsize + t->present;
 80}

 81
 82static void
 83rotate (struct node *t, struct node *f)
 84{
 85struct node **ftlink, **alink, *a;
 86
 87if (f->== t)
 88    {
 89      ftlink = &f->r;
 90      alink = &t->l;
 91    }

 92else
 93    {
 94      ftlink = &f->l;
 95      alink = &t->r;
 96    }

 97
 98t->= f->f;
 99if (f->f)
100    {
101      if (f->f->== f)
102f->f->= t;
103      else
104f->f->= t;
105    }

106
107= *alink;
108*ftlink = a;
109if (a)
110    a->= f;
111
112*alink = f;
113f->= t;
114
115fix_size (f);
116fix_size (t);
117}

118
119static void
120zigzig (struct node *t, struct node *f, struct node *gf)
121{
122struct node **gfflink, **ftlink, **blink, **clink, *b, *c;
123if (gf->== f)
124    {
125      gfflink = &gf->r;
126      ftlink = &f->r;
127      blink = &f->l;
128      clink = &t->l;
129    }

130else
131    {
132      gfflink = &gf->l;
133      ftlink = &f->l;
134      blink = &f->r;
135      clink = &t->r;
136    }

137
138= *blink;
139= *clink;
140
141t->= gf->f;
142if (gf->f)
143    {
144      if (gf->f->== gf)
145gf->f->= t;
146      else
147gf->f->= t;
148    }

149
150*clink = f;
151f->= t;
152
153*blink = gf;
154gf->= f;
155
156*gfflink = b;
157if (b)
158    b->= gf;
159
160*ftlink = c;
161if (c)
162    c->= f;
163
164fix_size (gf);
165fix_size (f);
166fix_size (t);
167}

168
169static void
170zigzag (struct node *t, struct node *f, struct node *gf)
171{
172struct node **gfflink, **ftlink, **blink, **clink, *b, *c;
173if (gf->== f)
174    {
175      gfflink = &gf->l;
176      ftlink = &f->r;
177      blink = &t->l;
178      clink = &t->r;
179    }

180else
181    {
182      gfflink = &gf->r;
183      ftlink = &f->l;
184      blink = &t->r;
185      clink = &t->l;
186    }

187
188= *blink;
189= *clink;
190
191t->= gf->f;
192if (gf->f)
193    {
194      if (gf->f->== gf)
195gf->f->= t;
196      else
197gf->f->= t;
198    }

199
200*clink = gf;
201gf->= t;
202
203*blink = f;
204f->= t;
205
206*gfflink = c;
207if (c)
208    c->= gf;
209
210*ftlink = b;
211if (b)
212    b->= f;
213
214fix_size (gf);
215fix_size (f);
216fix_size (t);
217}

218
219static void
220double_rotate (struct node *t, struct node *f, struct node *gf)
221{
222if ((gf->== f) == (f->== t))
223    zigzig (t, f, gf);
224else
225    zigzag (t, f, gf);
226}

227
228static void
229splay (struct node *t)
230{
231struct node *f, *gf;
232
233while (t->f)
234    {
235      f = t->f;
236
237      gf = f->f;
238      if (!gf)
239{
240   clean_reverse (f);
241   clean_reverse (t);
242   rotate (t, f);
243   return;
244}

245      clean_reverse (gf);
246      clean_reverse (f);
247      clean_reverse (t);
248
249      double_rotate (t, f, gf);
250    }

251
252clean_reverse (t);
253}

254
255static int
256rotfirst_and_delete (struct node *t)
257{
258int pos;
259
260splay (t);
261/*printf ("After splay: ");
262dump_path();
263printf ("\n");*/

264if (t->l)
265    {
266      t->l->reverse = !t->l->reverse;
267      pos = t->l->size;
268    }

269else
270    pos = 0;
271
272t->present = 0;
273t->size--;
274
275return pos;
276}

277
278static int
279cmp_input (const void *a, const void *b)
280{
281int va = *(int *) a;
282int vb = *(int *) b;
283
284if (input[va] != input[vb])
285    return input[va] - input[vb];
286
287return va - vb;
288}

289
290int
291main (void)
292{
293int i;
294
295while (1)
296    {
297      scanf ("%d"&n);
298      if (!n)
299return 0;
300
301      for (i = 0; i < n; i++)
302scanf ("%d"&input[i]);
303
304      for (i = 0; i < n; i++)
305ipermut[i] = i;
306
307      qsort (ipermut, n, sizeof (int), cmp_input);
308
309      for (i = 0; i < n; i++)
310permut[ipermut[i]] = i;
311
312/*      for (i = 0; i < n; i++)
313printf ("%d ", permut[i]);
314      printf ("\n");*/

315      for (i = 0; i < n; i++)
316{
317   path_nodes[permut[i]].reverse = 0;
318   path_nodes[permut[i]].size = i + 1;
319   path_nodes[permut[i]].present = 1;
320   path_nodes[permut[i]].l = i > 0 ? &path_nodes[permut[i-1]] : NULL;
321   path_nodes[permut[i]].r = NULL;
322   path_nodes[permut[i]].f = i < n - 1 ? &path_nodes[permut[i+1]] : NULL;
323}

324
325      for (i = 0; i < n; i++)
326{
327   /*dump_path ();*/
328   printf ("%d%c", rotfirst_and_delete (&path_nodes[i]) + i + 1, i+1 < n ? ' ' : '\n');
329}

330    }

331}

332
posted on 2008-08-31 00:49 雪竹的天空( theorix ) 閱讀(537) 評論(0)  編輯 收藏 引用

只有注冊用戶登錄后才能發(fā)表評論。
網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲国产精品嫩草影院| 欧美好骚综合网| 国产精品成人va在线观看| 在线视频欧美日韩| aa成人免费视频| 国产精品亚洲视频| 久久久亚洲精品一区二区三区 | 在线综合亚洲欧美在线视频| 日韩天堂av| 国产日韩亚洲| 亚洲国产精品嫩草影院| 欧美全黄视频| 欧美自拍偷拍| 欧美sm视频| 午夜亚洲伦理| 久久午夜国产精品| 在线一区观看| 久久蜜桃精品| 亚洲一区二区三区在线| 久久久久国产精品午夜一区| 一区二区精品在线| 欧美一区日韩一区| 99精品黄色片免费大全| 欧美亚洲免费高清在线观看| 亚洲精品久久久久久久久久久久久 | 亚洲视频一区| 久久久999成人| 亚洲线精品一区二区三区八戒| 欧美一区二区视频免费观看| 亚洲日本中文字幕免费在线不卡| 亚洲性视频网址| 亚洲经典一区| 欧美在线日韩| 亚洲欧美自拍偷拍| 欧美伦理91i| 欧美 日韩 国产一区二区在线视频| 欧美日韩中文字幕精品| 欧美福利视频一区| 亚洲裸体视频| 在线播放国产一区中文字幕剧情欧美 | 亚洲成色777777女色窝| 亚洲一二三级电影| 亚洲欧美偷拍卡通变态| 国产精品毛片a∨一区二区三区|国 | 亚洲国产日韩欧美| 亚洲免费久久| 久久九九精品| 欧美伊人久久大香线蕉综合69| 嫩草国产精品入口| 久久天天狠狠| 国产欧美精品在线播放| 一本色道久久综合亚洲精品按摩| 亚洲国产精品一区二区第一页| 亚洲午夜影视影院在线观看| 亚洲精品在线视频观看| 久久这里有精品视频| 久久久综合网站| 国产亚洲二区| 久久成人精品电影| 久久久久久97三级| 国产亚洲在线| 欧美综合激情网| 久久精品水蜜桃av综合天堂| 国产模特精品视频久久久久| 亚洲天堂av高清| 亚洲欧美视频在线观看视频| 国产精品久久久久aaaa樱花| 一区二区欧美在线观看| 亚洲午夜精品在线| 国产精品老牛| 欧美一区二区视频在线| 久久久久国内| 亚洲国产成人av| 欧美激情按摩| 一区二区福利| 久久精品72免费观看| 激情婷婷亚洲| 免费欧美日韩| 99精品久久| 久久九九热re6这里有精品| 红桃视频国产一区| 美脚丝袜一区二区三区在线观看 | 在线观看一区二区视频| 美女啪啪无遮挡免费久久网站| 欧美国产日韩免费| 一区二区黄色| 国产亚洲一区二区三区| 欧美不卡一卡二卡免费版| 夜久久久久久| 久久久噜噜噜久噜久久 | 国产一区二区三区的电影| 麻豆成人91精品二区三区| 99re6这里只有精品| 久久高清福利视频| 亚洲精选中文字幕| 国产美女扒开尿口久久久| 久久精品动漫| 99精品欧美一区| 久久久亚洲人| 亚洲天堂男人| 伊人狠狠色j香婷婷综合| 欧美日韩国产精品一卡| 香蕉久久夜色| 亚洲精品国产精品国自产观看| 欧美在线国产| 亚洲裸体视频| 国产亚洲欧美日韩一区二区| 免费一级欧美片在线播放| 亚洲视频网在线直播| 女人色偷偷aa久久天堂| 午夜精品99久久免费| 亚洲经典一区| 亚洲美女诱惑| 欧美不卡福利| 久久av资源网站| 一区二区三区日韩在线观看| 韩国免费一区| 国产精品一国产精品k频道56| 欧美成人在线影院| 久久久999| 欧美一区二区三区在线视频| 亚洲精品久久久久久下一站| 久久综合给合| 久久久久久久精| 午夜精品理论片| 亚洲视频中文字幕| 亚洲免费观看高清在线观看 | 久久精品女人| 亚洲女同同性videoxma| 一本大道久久a久久综合婷婷| 在线观看国产成人av片| 国产欧美一区二区三区在线看蜜臀| 欧美精品日韩| 欧美欧美午夜aⅴ在线观看| 麻豆久久精品| 玖玖玖国产精品| 久久噜噜噜精品国产亚洲综合| 午夜亚洲影视| 校园春色国产精品| 欧美一区二区| 久久超碰97人人做人人爱| 欧美一级二级三级蜜桃| 午夜亚洲视频| 久久久久久久激情视频| 久久久99精品免费观看不卡| 欧美一区二区在线播放| 欧美在线黄色| 久久亚洲私人国产精品va媚药| 久久久久久久波多野高潮日日| 性娇小13――14欧美| 久久精品一区中文字幕| 久久先锋影音av| 免费永久网站黄欧美| 欧美剧在线观看| 欧美午夜电影一区| 国产日韩成人精品| 狠狠爱综合网| 亚洲精品一区在线观看| 一区二区三区四区国产| 午夜欧美大尺度福利影院在线看| 欧美与黑人午夜性猛交久久久| 久久精品国产99精品国产亚洲性色| 欧美专区亚洲专区| 欧美成va人片在线观看| 亚洲精品少妇30p| 亚洲影院免费| 久久精品人人做人人爽| 欧美电影在线观看| 国产精品区一区二区三| 国产日韩欧美视频| 亚洲人成亚洲人成在线观看 | 国产精品日韩欧美综合| 影音先锋亚洲一区| 一区二区欧美日韩| 久久免费视频网站| 亚洲乱码视频| 欧美影院成人| 欧美日韩国产区一| 国产一区二区按摩在线观看| 亚洲黄色成人网| 亚洲欧美伊人| 亚洲第一精品电影| 亚洲欧美精品伊人久久| 欧美1区2区| 国产精品一区久久久| 亚洲欧洲免费视频| 欧美中文字幕视频在线观看| 亚洲国产欧美日韩精品| 亚洲欧美区自拍先锋| 欧美成年人网站| 一区二区三区视频在线观看| 久久精品日韩| 国产精品卡一卡二| 日韩视频在线一区二区三区| 久久精品免视看| 亚洲视频中文字幕| 欧美日韩精品久久久| 亚洲成人在线网| 久久久综合网站| 亚洲一区一卡|