fork(2) download
copy 
  1.     import java.io.*;
  2.     import java.util.*;
  3.     import java.lang.*;
  4.  
  5.     class Stack{
  6.     	private int a[];
  7.     	private int top;
  8.     	private int size;
  9.     	public Stack(int n){
  10.     		size=n;
  11.     		a=new int[size];
  12.     		for(int i=0;i<size;i++){
  13.     			a[i]=0;
  14.     		}
  15.     		top=-1;
  16.     	}
  17.  
  18.     	public boolean push(int k){
  19.     		if(top<size-1){
  20.     			a[++top]=k;
  21.     			return true;
  22.     		}else{
  23.     			//System.out.println("Overflow error");
  24.     			return false;
  25.     		}
  26.     	}
  27.  
  28.     	public boolean pop(){
  29.     		if(top>-1){
  30.     			top--;
  31.     			return true;
  32.     		}else{
  33.     			//System.out.println("Underflow error");
  34.     			return false;
  35.     		}
  36.     	}
  37.  
  38.     	public int getSize(){
  39.     		return size;
  40.     	}
  41.  
  42.     	public int getTop(){
  43.     		return top;
  44.     	}
  45.  
  46.     	public int peak(){
  47.     		return a[top];
  48.     	}
  49.  
  50.     	public boolean isEmpty(){
  51.     		return top==-1;
  52.     	}
  53.  
  54.     	public void print(){
  55. 			char[] line = new char[top+1];
  56. 			for(int i=0;i<=top;i++){
  57. 				line[i] = (char)(a[i]+'0');
  58. 			}
  59. 			System.out.println(line);
  60.     	}
  61.     }
  62.  
  63.     class Queue{
  64.     	private int a[];
  65.     	private int front;
  66.     	private int rear;
  67.     	private int size;
  68.  
  69.     	public Queue(int n){
  70.     		size=n;
  71.     		a= new int[size];
  72.     		front=-1;
  73.     		rear=-1;
  74.     	}
  75.  
  76.     	public boolean enqueue(int k){
  77.  
  78.     		if(isFull()){
  79.     			System.out.println("Overflow Error");
  80.     			return false;
  81.     		}
  82.     		if(isEmpty()){
  83.     			++rear;
  84.     		}
  85.     		++front;
  86.     		if(front==size){
  87.     			front=0;
  88.     		}
  89.  
  90.     		a[front]=k;
  91.     		return true;
  92.     	}
  93.  
  94.     	public boolean dequeue(){
  95.     		if(isEmpty()){
  96.     			System.out.println("Underflow Error");
  97.     			return false;
  98.     		}
  99.  
  100.     		if(front==rear){
  101.     			front=-1;
  102.     			rear=-1;
  103.     		}else{
  104.     			++rear;
  105.     			if(rear==size){
  106.     				rear=0;
  107.     			}
  108.     		}
  109.  
  110.     		return true;
  111.     	}
  112.  
  113.     	public boolean isFull(){
  114.     		return rear==front+1||(rear==0 && front==size-1);
  115.     	}
  116.  
  117.     	public boolean isEmpty(){
  118.     		return rear==-1 && front==-1;
  119.     	}
  120.  
  121.     	public int getFront(){
  122.     		return front;
  123.     	}
  124.  
  125.     	public int getRear(){
  126.     		return rear;
  127.     	}
  128.  
  129.     	public int getSize(){
  130.     		return size;
  131.     	}
  132.  
  133.     	public int peakFront(){
  134.     		return a[front];
  135.     	}
  136.  
  137.     	public int peakRear(){
  138.     		return a[rear];
  139.     	}
  140.  
  141.     	public void print(){
  142.     		if(front==-1 && rear==-1){
  143.     			System.out.println("");
  144.     			return;
  145.     		}
  146.     		int i=rear-1;
  147.     		do{
  148.     			i++;
  149.     			if(i==size){
  150.     				i=0;
  151.     			}
  152.     			System.out.print(a[i]+" ");
  153.     		}while(i!=front);
  154.     		System.out.print("\n");
  155.     	}
  156.     }
  157.  
  158.     public class Main{
  159.  
  160.     	public static void main(String[] args) throws java.lang.Exception  {
  161.         	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  162.         	int t = Integer.parseInt(br.readLine());
  163.  
  164.     		for(int t_=0;t_<t;t_++){
  165.     			int n = Integer.parseInt(br.readLine());
  166.  
  167.     			Stack digits=new Stack(n);
  168.     			char[] line = br.readLine().toCharArray();
  169.     			for(int i=0;i<line.length;i++){
  170.     				if ((line[i] >= '0') & (line[i] <='9')){
  171.     					digits.push(line[i]-'0');
  172.     				}
  173.     			}
  174.  
  175.     			Queue popped=new Queue(n);
  176.     			popped.enqueue(digits.peak());
  177.     			digits.pop();
  178.     			int next;
  179.     			boolean flag=false;
  180.     			while(!digits.isEmpty()){
  181.     				next=digits.peak();
  182.     				if(next>=popped.peakFront()){
  183.     					popped.enqueue(next);
  184.     					digits.pop();
  185.     				}else{
  186.     					flag=true;
  187.     					break;
  188.     				}
  189.     			}
  190.  
  191.     			if(flag){
  192.     				int a=digits.peak();
  193.     				digits.pop();
  194.     				Queue temp=new Queue(n);
  195.     				int b=0;
  196.     				while(!popped.isEmpty()){
  197.     					if(popped.peakRear()<a || !flag){
  198.     						temp.enqueue(popped.peakRear());
  199.     						popped.dequeue();
  200.     					}else{
  201.     						temp.enqueue(a);
  202.     						b=popped.peakRear();
  203.     						popped.dequeue();
  204.     						flag=false;
  205.     					}
  206.     				}
  207.     				if(flag){
  208.     					System.out.println("-1");
  209.     				}else{
  210.     					digits.push(b);
  211.     					while(!temp.isEmpty()){
  212.     						digits.push(temp.peakRear());
  213.     						temp.dequeue();
  214.     					}
  215.     					digits.print();
  216.     				}
  217.  
  218.     			}
  219.     		}
  220.  
  221.     		br.close();
  222.  
  223.     	}
  224.     }
Success #stdin #stdout 0.04s 2184192KB
comments (?)
stdin
copy 
3
5
1 5 4 8 3
3
3 2 1
10
1 4 7 4 5 8 4 1 2 6
stdout
copy 
15834
1474584162
https://ideone.com/4YND67
problem JNEXT, based on SPOJ submission 22910668 (JAVA), 2018-12-20 01:07:29
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!