264A.md (1739B)
1 Source: https://codeforces.com/problemset/problem/264/A 2 3 A. Escape from Stones 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Squirrel Liss lived in a forest peacefully, but unexpected trouble happens. Stones fall from a mountain. Initially Squirrel Liss occupies an interval [0, 1]. Next, *n* stones will fall and Liss will escape from the stones. The stones are numbered from 1 to *n* in order. 22 23 The stones always fall to the center of Liss's interval. When Liss occupies the interval [*k* - *d*, *k* + *d*] and a stone falls to *k*, she will escape to the left or to the right. If she escapes to the left, her new interval will be [*k* - *d*, *k*]. If she escapes to the right, her new interval will be [*k*, *k* + *d*]. 24 25 You are given a string *s* of length *n*. If the *i*-th character of *s* is "l" or "r", when the *i*-th stone falls Liss will escape to the left or to the right, respectively. Find the sequence of stones' numbers from left to right after all the *n* stones falls. 26 27 Input 28 29 The input consists of only one line. The only line contains the string *s* (1 ≤ |*s*| ≤ 106). Each character in *s* will be either "l" or "r". 30 31 Output 32 33 Output *n* lines — on the *i*-th line you should print the *i*-th stone's number from the left. 34 35 Examples 36 37 Input 38 39 ``` 40 llrlr 41 ``` 42 43 Output 44 45 ``` 46 3 47 5 48 4 49 2 50 1 51 ``` 52 53 Input 54 55 ``` 56 rrlll 57 ``` 58 59 Output 60 61 ``` 62 1 63 2 64 5 65 4 66 3 67 ``` 68 69 Input 70 71 ``` 72 lrlrr 73 ``` 74 75 Output 76 77 ``` 78 2 79 4 80 5 81 3 82 1 83 ``` 84 85 Note 86 87 In the first example, the positions of stones 1, 2, 3, 4, 5 will be , respectively. So you should print the sequence: 3, 5, 4, 2, 1.