All submissions for this problem are available.
There are N seats in a theatre, all of them in a single row. The seats are numbered from 1 to N. You are given two types of events:
- 1 — A person arrives. Persons are numbered from 1 in order of their arrival.
- 2 i — Person i leaves the theatre.
A person arriving in the theatre chooses a seat according to the following algorithm:
If the entire theatre is empty, the person will occupy seat 1.
Otherwise, he will occupy the seat which is farthest possible from any nearest seated persons. In other words, in the seat which maximizes the minimum distance to any other person currently seated. If there are many such seats, the person will occupy the leftmost of them.
InputThe first line of input contains 2 space-separated integers: the first is N, denoting the number of seats, and the second is Q, denoting the number of events. Then Q events follow in the format described above.
OutputFor each person arriving, output the seat number that he occupies.
- 1 ≤ N ≤ 1018
- 1 ≤ Q ≤ 2 * 105
- Each query is valid.
Input: 2 7 1 1 2 1 1 2 2 2 3 1 Output: 1 2 1 1
Initially both seats are empty (x denotes empty seat and number denotes id of person occupying it):
Query 1: Person #1 arrives and takes seat 1 (so output 1):
Query 2: Person #2 arrives and takes seat 2 (so output 2):
Query 3: Person #1 leaves:
Query 4: Person #3 arrives and takes seat 1 (so output 1):
Query 5: Person #2 leaves:
Query 6 Person #3 leaves:
Query 7: Person #4 arrives and takes seat 1 (so output 1):
|Tags||acmkol15, balajiganapath, maps, medium-hard, tree, tree-based|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.