# Poj Solution 3476

```http://poj.org/problem?id=3476

//* @author: <strong>Yeming&nbsp;Hu</strong>&quot;cslittleye@gmail.com&quot;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
BinaryHeap pq = new BinaryHeap();
String s = sc.next();
char previousChar = s.charAt(0);
Ball ball = new Ball(0+1);
BallSeq seq = new BallSeq(previousChar,0+1);
tail = seq;
seq.firstBall = ball;
seq.lastBall = ball;
seq.number++;
for(int i = 1; i < s.length(); i++)
{
char currentChar = s.charAt(i);
if(currentChar==previousChar)
{
ball = new Ball(i+1);
seq.lastBall.nextBall = ball;
//ball.previousBall = seq.lastBall;
seq.lastBall = ball;
seq.number++;
}else
{
previousChar = currentChar;
pq.offer(seq);
seq = new BallSeq(previousChar,i+1);
tail.nextBallSeq = seq;
seq.previousBallSeq = tail;
tail = seq;
ball = new Ball(i+1);
seq.firstBall = ball;
seq.lastBall = ball;
seq.number++;
}
}
pq.offer(seq);
while(true)
{
int size = pq.size();
if(size==0)
{
break;
}
seq = pq.poll();
if(seq.number==1)
{
break;
}
System.out.print(seq.color);
ball = seq.firstBall;
for(int i = 0; i < seq.number; i++)
{
System.out.print(" "+ball.position);
ball = ball.nextBall;
}
System.out.println();
{
{
}
}else if(seq == tail)
{
tail = seq.previousBallSeq;
if(tail !=null )
{
tail.nextBallSeq = null;
}
}else
{
BallSeq p = seq.previousBallSeq;
BallSeq n = seq.nextBallSeq;
if(p.color == n.color)
{
pq.remove(p);
pq.remove(n);
p.number += n.number;
p.lastBall.nextBall = n.firstBall;
//n.firstBall.previousBall = p.lastBall;
p.lastBall = n.lastBall;
p.nextBallSeq = n.nextBallSeq;
if(n != tail)
{
n.nextBallSeq.previousBallSeq = p;
}else
{
tail =p;
}
pq.offer(p);
}else
{
p.nextBallSeq = n;
n.previousBallSeq = p;
}
}
}
}
}

class BallSeq implements Comparable< BallSeq>
{
public char color;
public int number;
public int start;
public int position;
Ball firstBall;
Ball lastBall;
BallSeq previousBallSeq;
BallSeq nextBallSeq;
public BallSeq(char color, int start)
{
this.color = color;
this.start = start;
this.number = 0;
position = 0;
firstBall = null;
lastBall = null;
previousBallSeq = null;
nextBallSeq = null;
}
public int compareTo(BallSeq bs)
{
if(this.number == bs.number)
{
if(this.start == bs.start)
{
return 0;
}else if(this.start < bs.start)
{
return -1;
}else
{
return 1;
}
}else if(this.number < bs.number)
{
return 1;
}else
{
return -1;
}
}
}

class Ball
{
//Ball previousBall;
Ball nextBall;
int position;//position in the sequence
public Ball(int position)
{
this.position = position;
//previousBall = null;
nextBall = null;
}
}
class BinaryHeap
{
public static final int max = 1000000;
int count;
BallSeq[] segments;
public BinaryHeap()
{
count = 0;
segments = new BallSeq[max];
}
public void offer(BallSeq seq)
{
if(count == max - 1)
{
throw new RuntimeException("Full Heap");
}
count++;
int i = count;
while(i > 1 && segments[i/2].compareTo(seq) == 1)
{
segments[i] = segments[i/2];
segments[i].position = i;
i = i/2;
}
segments[i] = seq;
segments[i].position = i;
}
public void remove(BallSeq seq)
{
int i = seq.position;
while(i > 1)
{
segments[i] = segments[i/2];
segments[i].position = i;
i = i/2;
}
segments[i] = seq;
segments[i].position = i;
poll();
}
public BallSeq poll()
{
if(count == 0)
{
throw new RuntimeException("Empty Heap");
}
BallSeq result = segments;
BallSeq last = segments[count];
count--;
int i =1;
while(2*i <= count)
{
int child = 2*i;
if(child + 1 <= count && segments[child].compareTo(segments[child+1]) == 1)
{
child += 1;
}
if(last.compareTo(segments[child]) == -1)
{
break;
}
segments[i] = segments[child];
segments[i].position = i;
i = child;
}
segments[i] = last;
segments[i].position = i;
return result;
}
public int size()
{
return count;
}
public int capacity()
{
return max;
}
}
```
This entry was posted in poj. Bookmark the permalink.