Swapping mismatches

Problem code: C1

All submissions for this problem are available.

You are given a sequence w of integers. A mismatch is any such pair of neighbouring elements of sequence w[i] and w[i+1], that w[i]>w[i+1]+1. As long as there is any mismatch, you solve it by swapping the mismatching numbers. Given an input sequence, calculate one of the possible output mismatch-less sequences obtained by successively solving mistmatches by swapping.

Input

First - 1<=t<=10 - the number of tests. For each test: first - 1<=n<=100000. Then, n nonnegative integers.

Output

For each test, you should output exactly n integers.

Example

Input:
2
4
4 3 2 1
4
4 3 1 2

Output:
4 3 2 1
1 4 3 2

Author: admin
Date Added: 20-04-2009
Time Limit: 1 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

punbhatia @ 12 May 2009 02:47 PM

I am able to run my code on my home laptop for all the given test cases in the 800ms to 2.5 second range. Why are my submissions timing out? Chef? Care to comment?

jvimal @ 12 May 2009 06:41 PM

@Puneet: The time limit for this problem is 1 second, and that 1 second is for all the test cases in a given "run". (a "run" is an invocation of your program for one input file.) Also, the run-time sometimes depends on the server load. A O(n log n) solution should pass, if the constant factor associated with the (log n) operation is small. And, as an example, the STL data structures like set, map, etc. have a high constant factor associated with them.

nandish_83 @ 1 Jul 2009 02:21 AM

I have tried comparing the ouput of my solution with the accepted programs output. I am unable to find any difference in the output for any kind of input. Please share if u have any trivial test cases for this problem

i0exception @ 1 Jul 2009 02:26 AM

@nandish The solutions are available. You can view them and test them on random as well as some carefully crafted test cases by you. You can construct trivial test cases and verify the correct output by running any of the accepted submissions against them.

nandish_83 @ 1 Jul 2009 02:41 AM

@Anirudhaa, thanks for the reply.

Hi moderators, I have a

mohammad @ 17 Jan 2010 06:23 PM

Hi moderators,

I have a query..my submission fails saying wrong answer. I am just wondering is there more than one solution to the problem...i mean depending upon algorithm can the output change. Like for a input

4 3 1 2
output can be 4 1 3 2 or 1 2 3 4. Right?? Please guide...or suggest some way to test it exhaustively. I am confident of my code

For some of test cases my

Bhoomit @ 27 Jun 2010 07:39 PM

For some of test cases my solution works fine can someone tell me some corner cases ??

i tried with

1

8

8 7 6 3 4 1 2 5

my solution works fine

but still getting wrong ans while upload..:(

I did sorting but it gives

kriateive @ 9 Jan 2011 04:54 PM

I did sorting but it gives WA. any clue?

For those having trouble

msg555 @ 15 Jan 2011 01:48 AM

For those having trouble passing the time limit on this problem:

I too was having trouble solving this problem under the time limit until I switched from using cin/cout/endl to using scanf/printf.

Is this problem's solution AC

moshu123 @ 24 Feb 2011 02:30 PM

Is this problem's solution AC in java too in 1 s.

 

Since I am not able to find any mechanism in java to print 10*100000 numbers in 1 s, though the computation takes only 200 ms for 10 test cases with n=100000.

can we please get more

dee @ 12 Jul 2011 09:22 PM
can we please get more testcases

can any body tell me ?what

punitmundra @ 3 Oct 2011 04:38 PM
can any body tell me ?what the error in my code....

my program is giving perfect

r1r33 @ 8 Jan 2012 07:40 PM
my program is giving perfect ansr 4 each nd every testcase thn why it is nt being accepted?????

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions