oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

adjacentswaps Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

statement.html

Problem Statement

Physicist S has an array. He wants to sort the array in increasing order. However, as he is very lazy, he will only swap two adjacent elements in the array, and he wishes to have the array sorted in the minimum number of steps.

Help Physicist S by writing a program that tells him how to sort his array.

Input

The first line of input contains a single integer, N, the size of Physicist S's array.

The second line of input contains N integers, representing Physicist S's array.

Output

The first line of output should contain a single integer, ans, the minimum number of swaps required to sort the array.

The next ans lines of input should contain one integer each, i, denoting a swap between the ith and (i + 1)th element. If 1 ≤ i < N is not satisfied, you will receive a wrong answer verdict.

Limits

For all test cases, 1 ≤ N ≤ 100. All elements in the array are distinct and are integers from 1 to N.

Scoring

If the sequence of swaps you present does not sort the array, you will not receive any points.

Otherwise, your score for that test case is given by 50 + 50 * opt / ans, where opt is the optimal number of swaps.

Your final score is the minimum score for all test cases.

Sample Input

3
3 1 2

Sample Output

2
1
2

Explanation

Swapping the 1st and 2nd elements, followed by the 2nd and 3rd elements, sorts the array. This is the minimum number of swaps.

Tags

Greedy, Sorting

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100151s256MBMinimum
2011s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o adjacentswaps -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.