CSES - HIIT Open 2018 - Results
 Task: Coins Sender: HIIT AND RUN Submission time: 2018-05-26 14:47:44 +0300 Language: Java Status: READY Result: TIME LIMIT EXCEEDED
Test results
testverdicttime
#1--details
#2--details
#3--details
#4--details
#5--details

Code

```//package lol;

import java.util.*;

public class C {

public static void main(String[] args) {
Scanner io = new Scanner(System.in);
int n = io.nextInt();
TreeSet<Integer> l = new TreeSet<>();
TreeSet<Integer> r = new TreeSet<>();
List<Integer> backtrackActions = new ArrayList<>(2*n);
for (int i=0; i<n; i++) {
int coin = io.nextInt();
int leftOrRight = io.nextInt();
}

// asetetaan "to" se mis on isoin
TreeSet<Integer> to = r;
TreeSet<Integer> from = l;
if (!l.isEmpty()) {
if (r.isEmpty() || l.last() > r.last()) {
to = l;
from = r;
}
}
Integer largest = to.last();

// iterate vikavastaus -> actionit -> 2.vika vastaus -> actionit -> ...
List<String> ans = new ArrayList<>(n);
PriorityQueue<Integer> pq = new PriorityQueue<>();
int countRemovedSmalls = 0;
int i=backtrackActions.size()-1;
while (true) {
int smallestInFrom = (from.isEmpty() ? 0 : from.first());

//System.out.println("smallestInFrom " + smallestInFrom);

//System.out.println("to == r ? " + (to == r ? true : false));

// vastaus
int countSmallerThanFromSmallest = Math.max(0, smallestInFrom - 1 - countRemovedSmalls);
int isojaMatchaavia = to.size() - countSmallerThanFromSmallest;

//System.out.println("debug " + isojaMatchaavia + " " + from.size() + " " + countSmallerThanFromSmallest);

if (isojaMatchaavia >= from.size()) ans.add(to == r ? "<" : ">");

// actioni alkaa
if (i <= 2) break;
int leftOrRight = backtrackActions.get(i--);
int coin = backtrackActions.get(i--);
//System.out.println("Removing " + coin);

if (coin < smallestInFrom) {
to.remove(coin);
countRemovedSmalls++;
} else if (coin == smallestInFrom) {
from.remove(coin);
countRemovedSmalls++;
int newSmallest = (from.isEmpty() ? 0 : from.first());
while (!pq.isEmpty() && pq.peek() < newSmallest) {
pq.poll();
countRemovedSmalls++;
}
} else if (coin == largest) {
to.remove(coin);
largest = (to.isEmpty() ? null : to.last());
//System.out.println("largest " + largest);
if (largest == null || (!from.isEmpty() && from.last() > largest)) {
// swap to and from
TreeSet<Integer> helper = from;
from = to;
to = helper;
largest = to.last();
}
} else {
if (leftOrRight == 2) r.remove(coin);
else l.remove(coin);
}
}

Collections.reverse(ans);
for (String s : ans) System.out.println(s);
}
}
```

Verdict:

input
200000
175878 1
146174 1
4939 2
181388 1
...

correct output
>
>
>
>
>
...

user output
(empty)

Verdict:

input
200000
1 2
2 1
3 2
4 1
...

correct output
<
>
<
>
<
...

user output
(empty)

Verdict:

input
200000
1 1
2 1
3 1
4 1
...

correct output
>
>
>
>
>
...

user output
(empty)

Verdict:

input
200000
1 1
2 1
3 1
4 1
...

correct output
>
>
>
>
>
...

user output
(empty)

Verdict:

input
200000
188909 2
58944 1
26824 1
143263 2
...

correct output
<
<
?
<
<
...

user output
(empty)