[POI2010] KOL-Railway
题目描述
A railroad siding consists of two (dead-end) sidetracks 1 and 2.
The siding is entered by track A, and left by track B (see figure below).
There are 
cars on track A, numbered from 
to 
.
They are arranged in such a way that they enter the siding in the order 
.
The cars are to be transferred to the siding, so that they leave it by track B in the order 
.
Each car is to be transferred once from track A to one of the sidetracks 1 or 2, and later (possibly after some transfers of the remaining cars) once from that sidetrack to the track B.
The sidetracks are long enough to store even the longest trains, so there is no need to worry about their capacity.
数据范围10W的双栈排序..双栈排序是啥呢？给你一个序列和两个栈，每次你可以把序列头入到两个栈的任意一个，或者把两个栈的任意一个弹出到最终序列，最后要求最终序列是有序的，求一种字典序最小的入栈方案
输入格式
The first line of the standard input holds one integer 
(
) that denotes the number of cars for transfer.
The second line stores the numbers 
that are a permutation of 
(i.e., each 
belongs to 
, and all these numbers are unique), separated by single spaces.
输出格式
The first line of the standard output should contain the word TAK (yes in Polish) if there is a way of transferring the cars so that they enter track B in the order 
, or the word NIE (no in Polish) if it is impossible.
If the answer is TAK, the second line should give, separated by single spaces, the numbers of sidetracks (1 or 2) to which successive cars 
are moved in a correct transfer.
If there are several ways of making the transfer, choose one arbitrarily.
4
1 3 4 2
TAK
1 1 2 1
提示