1.


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
* Angewandte Mathematik, SS11 Problem: 11525 - Permutations Link:
* http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2520
*
* @author Benedikt Z¨nnchen
* @author Erik Wenzel
* @version 1.0, 29/04/2011
*
* Method : Combinatorics, Memorizing
* Status : Accepted
* Runtime: 2.596
*/

public class Main
{

public static void main(String[] args) throws IOException
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int cases = Integer.parseInt(reader.readLine());
MyList cArray;
StringBuilder builder = new StringBuilder();
;

while (cases > 0)
{
cases--;
int k = Integer.parseInt(reader.readLine());
cArray = new MyList(k);
for (int i = 1; i <= k; i++)
{
cArray.add(i);
}
boolean space = false;
String[] split = reader.readLine().split(" ");
for (int i = 0; i < k; i++)
{
int s = Integer.parseInt(split[i]);
// vor erstem zeichen kein leerzeichen
if (space)
{
builder.append(" ");
}
else
{
space = true;
}
builder.append(cArray.remove(s));
}
builder.append("\n");
}
System.out.print(builder.toString());
}

/**
* Eigenen Liste f¾r primitiven Datentyp int
* @author Benedikt Z¨nnchen
* @author Erik Wenzel
*
*/
private static class MyList implements Cloneable
{
int size, lastIndex, firstIndex;
private int array[];

private MyList(int size)
{
this.size = size;
array = new int[size];
lastIndex = 0;
firstIndex = 0;
}

public boolean add(int element)
{
array[lastIndex++] = element;
return true;
}

/**
* Gleiche funktion wie ArrayList.remove(int)
* @param location
* @return wert der removed wurde
*/
public int remove(int location)
{
int size = lastIndex - firstIndex;
int result;
if (0 <= location && location < size)
{
if (location == size - 1)
{
result = array[--lastIndex];
array[lastIndex] = 0;
}
else if (location == 0)
{
result = array[firstIndex];
array[firstIndex++] = 0;
}
else
{
int elementIndex = firstIndex + location;
result = array[elementIndex];
if (location < size / 2)
{
System.arraycopy(array, firstIndex, array,
firstIndex + 1, location);
array[firstIndex++] = 0;
}
else
{
System.arraycopy(array, elementIndex + 1, array,
elementIndex, size - location - 1);
array[--lastIndex] = 0;
}
}
if (firstIndex == lastIndex)
{
firstIndex = lastIndex = 0;
}
}
else
{
throw new IndexOutOfBoundsException();
}
return result;
}

@Override
protected MyList clone() throws CloneNotSupportedException
{
MyList list = (MyList) super.clone();
list.array = array.clone();
return list;
}
}
}


2.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
* Angewandte Mathematik, SS11 Problem: 11525 - Permutations Link:
* http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2520
*
* @author Benedikt Z¨nnchen
* @author Erik Wenzel
* @version 1.0, 29/04/2011
*
* Method : Combinatorics, Memorizing
* Status : Accepted
* Runtime: 2.596
*/

public class Main
{

public static void main(String[] args) throws IOException
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int cases = Integer.parseInt(reader.readLine());
MyList cArray;
StringBuilder builder = new StringBuilder();
;

while (cases > 0)
{
cases--;
int k = Integer.parseInt(reader.readLine());
cArray = new MyList(k);
for (int i = 1; i <= k; i++)
{
cArray.add(i);
}
boolean space = false;
String[] split = reader.readLine().split(" ");
for (int i = 0; i < k; i++)
{
int s = Integer.parseInt(split[i]);
// vor erstem zeichen kein leerzeichen
if (space)
{
builder.append(" ");
}
else
{
space = true;
}
builder.append(cArray.remove(s));
}
builder.append("\n");
}
System.out.print(builder.toString());
}

/**
* Eigenen Liste f¾r primitiven Datentyp int
* @author Benedikt Z¨nnchen
* @author Erik Wenzel
*
*/
private static class MyList implements Cloneable
{
int size, lastIndex, firstIndex;
private int array[];

private MyList(int size)
{
this.size = size;
array = new int[size];
lastIndex = 0;
firstIndex = 0;
}

public boolean add(int element)
{
array[lastIndex++] = element;
return true;
}

/**
* Gleiche funktion wie ArrayList.remove(int)
* @param location
* @return wert der removed wurde
*/
public int remove(int location)
{
int size = lastIndex - firstIndex;
int result;
if (0 <= location && location < size)
{
if (location == size - 1)
{
result = array[--lastIndex];
array[lastIndex] = 0;
}
else if (location == 0)
{
result = array[firstIndex];
array[firstIndex++] = 0;
}
else
{
int elementIndex = firstIndex + location;
result = array[elementIndex];
if (location < size / 2)
{
System.arraycopy(array, firstIndex, array,
firstIndex + 1, location);
array[firstIndex++] = 0;
}
else
{
System.arraycopy(array, elementIndex + 1, array,
elementIndex, size - location - 1);
array[--lastIndex] = 0;
}
}
if (firstIndex == lastIndex)
{
firstIndex = lastIndex = 0;
}
}
else
{
throw new IndexOutOfBoundsException();
}
return result;
}

@Override
protected MyList clone() throws CloneNotSupportedException
{
MyList list = (MyList) super.clone();
list.array = array.clone();
return list;
}
}
}


------------------------------------------------------------------------------------------------------


1.

package acm_11525_permutation;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
* FWP, Ausgew¦hlte Probleme aus dem ACM Programming Contest, SS10
* Problem: acm_11525_permutation
* Link:
*
* @author Martin Lambeck
* @version 1.0, 23.10.2010
*
* Method : B-Tree
* Status : Accepted
* Runtime: 0.840
*/


public class Main
{
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static Node root;

public static void main(String... args) throws IOException
{
root = Node.init(1, 50001);


int cases = Integer.parseInt(reader.readLine());

for (int i = 0; i < cases; i++)
testcase();
}

public static void testcase() throws IOException
{
int k = Integer.parseInt(reader.readLine());
String[] si = reader.readLine().split(" ");

root.reset();


StringBuffer sol = new StringBuffer();

for (int i = 0; i < k; i++)
{
int n = Integer.parseInt(si[i]);
int d = root.get(n).num;

root.delete(d);

if (i > 0)
sol.append(" ");

sol.append(d);
}

System.out.println(sol.toString());

}
}

//B-Tree which allows to delete Items. Items can be accessed by index.
class Node
{
Node low = null; // left/lower subtree
Node high = null; // right/higher subtree
int num = -1; // number of this node
int lower = -1; // number of nodes in left subtree (incl. root of lower subtree)
int initLower = -1; // value of lower, if no node was deleted (used on reset())
boolean deleted = false; //this node was deleted

public Node (int n)
{
num = n;
}

public int count() //number of nodes in both subtrees
{
return (low != null ? low.count() + 1 : 0) + (high != null ? high.count() + 1 : 0);
}

public void reset()
{
lower = initLower;
deleted = false;

if (low != null)
low.reset();

if (high != null)
high.reset();
}

public void delete(int n) //delete Node where num==n
{
if (n == num)
deleted = true;

if (n < num)
lower--;

if (n < num)
low.delete(n);

if (n > num)
high.delete(n);
}

public Node get(int i) //get Node of INDEX i (starts with 0)
{
if ((i == lower) && !deleted)
return this;

if (i < lower)
return low.get(i);

return high.get(i - lower - (deleted ? 0 : 1));
}

static Node init(int from, int to)
{
Node nod;

int mid = (to + from) / 2;

nod = new Node(mid);

if ((mid-1) >= from)
nod.low = init(from, mid-1);

if ((mid+1) <= to)
nod.high = init(mid+1, to);

nod.initLower = (nod.low != null ? nod.low.count() + 1 : 0); //nodes in low-subtree
nod.lower = nod.initLower;

return nod;
}
}