CSES - Datatähti 2016 alku

Submission details
Task:	Bittipeli
Sender:	rxz9000
Submission time:	2015-10-11 00:55:26 +0300
Language:	Java
Status:	READY
Result:	0

Feedback
subtask	verdict	score
#1	WRONG ANSWER	0
#2	WRONG ANSWER	0
#3	WRONG ANSWER	0
#4	WRONG ANSWER	0

Test results
test	verdict	time	subtask
#1	ACCEPTED	0.17 s	1	details
#2	ACCEPTED	0.17 s	1	details
#3	ACCEPTED	0.17 s	1	details
#4	WRONG ANSWER	0.17 s	1	details
#5	ACCEPTED	0.17 s	1	details
#6	ACCEPTED	0.17 s	1	details
#7	ACCEPTED	0.17 s	1	details
#8	ACCEPTED	0.17 s	1	details
#9	ACCEPTED	0.17 s	1	details
#10	ACCEPTED	0.17 s	1	details
#11	ACCEPTED	0.17 s	1	details
#12	ACCEPTED	0.17 s	1	details
#13	ACCEPTED	0.17 s	1	details
#14	ACCEPTED	0.18 s	1	details
#15	ACCEPTED	0.17 s	1	details
#16	ACCEPTED	0.17 s	1	details
#17	ACCEPTED	0.16 s	1	details
#18	ACCEPTED	0.18 s	1	details
#19	WRONG ANSWER	0.18 s	1	details
#20	ACCEPTED	0.18 s	1	details
#21	ACCEPTED	0.17 s	2	details
#22	ACCEPTED	0.17 s	2	details
#23	ACCEPTED	0.17 s	2	details
#24	ACCEPTED	0.17 s	2	details
#25	ACCEPTED	0.18 s	2	details
#26	WRONG ANSWER	0.16 s	2	details
#27	WRONG ANSWER	0.18 s	2	details
#28	ACCEPTED	0.17 s	2	details
#29	ACCEPTED	0.17 s	2	details
#30	ACCEPTED	0.17 s	2	details
#31	ACCEPTED	0.19 s	2	details
#32	ACCEPTED	0.17 s	2	details
#33	ACCEPTED	0.18 s	2	details
#34	WRONG ANSWER	0.17 s	2	details
#35	ACCEPTED	0.17 s	2	details
#36	ACCEPTED	0.17 s	2	details
#37	ACCEPTED	0.17 s	2	details
#38	WRONG ANSWER	0.17 s	2	details
#39	ACCEPTED	0.19 s	2	details
#40	WRONG ANSWER	0.17 s	2	details
#41	ACCEPTED	0.17 s	3	details
#42	WRONG ANSWER	0.18 s	3	details
#43	WRONG ANSWER	0.19 s	3	details
#44	ACCEPTED	0.18 s	3	details
#45	WRONG ANSWER	0.17 s	3	details
#46	ACCEPTED	0.17 s	3	details
#47	ACCEPTED	0.17 s	3	details
#48	ACCEPTED	0.17 s	3	details
#49	WRONG ANSWER	0.17 s	3	details
#50	ACCEPTED	0.18 s	3	details
#51	WRONG ANSWER	0.18 s	3	details
#52	ACCEPTED	0.18 s	3	details
#53	ACCEPTED	0.17 s	3	details
#54	WRONG ANSWER	0.17 s	3	details
#55	ACCEPTED	0.19 s	3	details
#56	ACCEPTED	0.19 s	3	details
#57	ACCEPTED	0.18 s	3	details
#58	WRONG ANSWER	0.19 s	3	details
#59	ACCEPTED	0.19 s	3	details
#60	WRONG ANSWER	0.18 s	3	details
#61	ACCEPTED	0.18 s	4	details
#62	ACCEPTED	0.17 s	4	details
#63	ACCEPTED	0.18 s	4	details
#64	WRONG ANSWER	0.18 s	4	details
#65	ACCEPTED	0.18 s	4	details
#66	ACCEPTED	0.17 s	4	details
#67	ACCEPTED	0.17 s	4	details
#68	ACCEPTED	0.17 s	4	details
#69	ACCEPTED	0.17 s	4	details
#70	WRONG ANSWER	0.17 s	4	details
#71	ACCEPTED	0.17 s	4	details
#72	ACCEPTED	0.18 s	4	details
#73	ACCEPTED	0.18 s	4	details
#74	ACCEPTED	0.17 s	4	details
#75	ACCEPTED	0.18 s	4	details
#76	ACCEPTED	0.27 s	4	details
#77	ACCEPTED	0.27 s	4	details
#78	WRONG ANSWER	0.24 s	4	details
#79	TIME LIMIT EXCEEDED	--	4	details
#80	ACCEPTED	0.78 s	4	details

Code

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class BittipeliTehtava {

    private static int fillList(List sequences, String str) {
        int nOfLongSequences = 0;
        
        int lengthMinusOne = str.length() - 1;
        for (int i = 0; i <= lengthMinusOne; i++) {
            if (i == lengthMinusOne || str.charAt(i) != str.charAt(i + 1)) {
                if (i > 0 && str.charAt(i) == str.charAt(i - 1)) {
                    sequences.add(new Sequence(str.charAt(i), true));
                    nOfLongSequences++;
                } else {
                    sequences.add(new Sequence(str.charAt(i), false));
                }
            }
        }
        
        return nOfLongSequences;
    }

    private static int removeSequences(List<Sequence> sequences) {
        int amountOfMoves = 0;
        Stack<Sequence> stackOfSequences = new Stack<>();

        int length = sequences.size();

        for (int i = 0; i < length; i++) {
            Sequence currentSequence = sequences.get(i);
            if (!stackOfSequences.isEmpty() && stackOfSequences.peek().token == currentSequence.token) {
                stackOfSequences.pop();
                amountOfMoves++;
            } else if (currentSequence.isLongerThan1) {
                amountOfMoves++;
            } else {
                stackOfSequences.push(currentSequence);
            }
        }

        if (stackOfSequences.isEmpty()) {
            return amountOfMoves;
        }
        return -1;
    }
    
    private static List<Integer> removeSequencesBackwards(List<Sequence> sequences, int nOfLongSequences) {
        List<Integer> moves = new LinkedList<>();
        Stack<Sequence> stackOfSequences = new Stack<>();
        
        int currentLongSequence = nOfLongSequences;

        for (int i = sequences.size() - 1; i >= 0; i--) {
            Sequence currentSequence = sequences.get(i);
            if (!stackOfSequences.isEmpty() && stackOfSequences.peek().token == currentSequence.token) {
                moves.add(currentLongSequence);         
                stackOfSequences.pop();
                if (stackOfSequences.isEmpty() || (i >= 1 && sequences.get(i - 1).isLongerThan1)) {
                    currentLongSequence--;
                }
            } else if (currentSequence.isLongerThan1) {
                moves.add(currentLongSequence);
                if (stackOfSequences.isEmpty() || (i >= 1 && sequences.get(i - 1).isLongerThan1)) {
                    currentLongSequence--;
                }
            } else {
                stackOfSequences.push(currentSequence);
            }
        }       
        if (stackOfSequences.isEmpty()) {
            return moves;
        }
        return null;
    }

    public static void main(String[] args) {

        IO io = new IO();
        String str = io.next();

        List<Sequence> sequences = new ArrayList<>();
        int nOfLongSequences = fillList(sequences, str);
        
        int moves1 = removeSequences(sequences);
        List<Integer> moves2 = removeSequencesBackwards(sequences, nOfLongSequences);
        
        StringBuilder output = new StringBuilder();
        
        if (moves1 > 0) {
            output.append("1");
            for (int i = 1; i < moves1; i++) {
                output.append(" 1");
            }
            io.println(moves1);
            io.println(output.toString());
        } else if (moves2 != null) {           
            output.append(moves2.get(0));
            int length = moves2.size();
            for (int i = 1; i < length; i++) {
                output.append(" ");
                output.append(moves2.get(i));
            }
            io.println(moves2.size());
            io.println(output.toString());
        } else {
            io.println("QAQ");
        }

        io.close();
    }
}

class Sequence {

    public final char token;
    public final boolean isLongerThan1;

    public Sequence(char token, boolean longerThan1) {
        this.token = token;
        this.isLongerThan1 = longerThan1;
    }
}

Test details

Test 1

Subtask: 1

Verdict: ACCEPTED

input
`1011001010` view save

correct output
`QAQ` view save

user output
`QAQ` view save

Test 2

Subtask: 1

Verdict: ACCEPTED

input
`0000001001` view save

correct output
`3 1 1 1` view save

user output
`3 1 1 1` view save

Test 3

Subtask: 1

Verdict: ACCEPTED

input
`0111011100` view save

correct output
`3 2 1 1` view save

user output
`4 1 1 1 1` view save

Test 4

Subtask: 1

Verdict: WRONG ANSWER

input
`0100100100` view save

correct output
`4 2 1 1 1` view save

user output
`QAQ` view save

Test 5

Subtask: 1

Verdict: ACCEPTED

input
`1110010110` view save

correct output
`4 2 1 1 1` view save

user output
`4 3 3 2 1` view save

Test 6

Subtask: 1

Verdict: ACCEPTED

input
`1111110110` view save

correct output
`3 1 1 1` view save

user output
`3 1 1 1` view save

Test 7

Subtask: 1

Verdict: ACCEPTED

input
`0011110001` view save

correct output
`3 1 2 1` view save

user output
`3 3 2 1` view save

Test 8

Subtask: 1

Verdict: ACCEPTED

input
`0111111000` view save

correct output
`2 1 1` view save

user output
`2 1 1` view save

Test 9

Subtask: 1

Verdict: ACCEPTED

input
`1111111100` view save

correct output
`2 1 1` view save

user output
`2 1 1` view save

Test 10

Subtask: 1

Verdict: ACCEPTED

input
`1000010011` view save

correct output
`3 2 1 1` view save

user output
`4 1 1 1 1` view save

Test 11

Subtask: 1

Verdict: ACCEPTED

input
`1101110000` view save

correct output
`3 1 1 1` view save

user output
`3 1 1 1` view save

Test 12

Subtask: 1

Verdict: ACCEPTED

input
`1101101100` view save

correct output
`4 1 2 1 1` view save

user output
`5 1 1 1 1 1` view save

Test 13

Subtask: 1

Verdict: ACCEPTED

input
`0100111110` view save

correct output
`3 1 1 1` view save

user output
`3 1 1 1` view save

Test 14

Subtask: 1

Verdict: ACCEPTED

input
`1101001011` view save

correct output
`4 2 2 2 1` view save

user output
`5 1 1 1 1 1` view save

Test 15

Subtask: 1

Verdict: ACCEPTED

input
`1110110010` view save

correct output
`4 1 2 1 1` view save

user output
`4 3 2 2 1` view save

Test 16

Subtask: 1

Verdict: ACCEPTED

input
`0011011100` view save

correct output
`3 3 2 1` view save

user output
`4 1 1 1 1` view save

Test 17

Subtask: 1

Verdict: ACCEPTED

input
`1100101011` view save

correct output
`QAQ` view save

user output
`QAQ` view save

Test 18

Subtask: 1

Verdict: ACCEPTED

input
`1101100111` view save

correct output
`3 2 2 1` view save

user output
`4 1 1 1 1` view save

Test 19

Subtask: 1

Verdict: WRONG ANSWER

input
`0110000100` view save

correct output
`3 2 1 1` view save

user output
`QAQ` view save

Test 20

Subtask: 1

Verdict: ACCEPTED

input
`0000101000` view save

correct output
`QAQ` view save

user output
`QAQ` view save

Test 21

Subtask: 2

Verdict: ACCEPTED

input
`1110010100` view save

correct output
`QAQ` view save

user output
`QAQ` view save

Test 22

Subtask: 2

Verdict: ACCEPTED

input
`1110010000` view save

correct output
`3 2 1 1` view save

user output
`3 3 2 1` view save

Test 23

Subtask: 2

Verdict: ACCEPTED

input
`1001101100` view save

correct output
`4 1 1 1 1` view save

user output
`4 1 1 1 1` view save

Test 24

Subtask: 2

Verdict: ACCEPTED

input
`0000000111` view save

correct output
`2 1 1` view save

user output
`2 1 1` view save

Test 25

Subtask: 2

Verdict: ACCEPTED

input
`0011111110` view save

correct output
`2 2 1` view save

user output
`2 2 1` view save

Test 26

Subtask: 2

Verdict: WRONG ANSWER

input
`1100101100` view save

correct output
`4 2 1 1 1` view save

user output
`QAQ` view save

Test 27

Subtask: 2

Verdict: WRONG ANSWER

input
`0111101110` view save

correct output
`3 2 1 1` view save

user output
`QAQ` view save

Test 28

Subtask: 2

Verdict: ACCEPTED

input
`0000011011` view save

correct output
`3 2 1 1` view save

user output
`3 3 2 1` view save

Test 29

Subtask: 2

Verdict: ACCEPTED

input
`1110011101` view save

correct output
`3 3 2 1` view save

user output
`3 3 2 1` view save

Test 30

Subtask: 2

Verdict: ACCEPTED

input
`0001011011` view save

correct output
`4 1 1 1 1` view save

user output
`4 1 1 1 1` view save

Test 31

Subtask: 2

Verdict: ACCEPTED

input
`0010110011` view save

correct output
`4 1 1 1 1` view save

user output
`4 1 1 1 1` view save

Test 32

Subtask: 2

Verdict: ACCEPTED

input
`0011100000` view save

correct output
`2 2 1` view save

user output
`3 1 1 1` view save

Test 33

Subtask: 2

Verdict: ACCEPTED

input
`1110100110` view save

correct output
`4 1 1 1 1` view save

user output
`4 1 1 1 1` view save

Test 34

Subtask: 2

Verdict: WRONG ANSWER

input
`0110110111` view save

correct output
`4 2 1 1 1` view save

user output
`QAQ` view save

Test 35

Subtask: 2

Verdict: ACCEPTED

input
`1110110010` view save

correct output
`4 1 2 1 1` view save

user output
`4 3 2 2 1` view save

Test 36

Subtask: 2

Verdict: ACCEPTED

input
`110011001100110011001010101010...` view save

correct output
`QAQ` view save

user output
`QAQ` view save

Test 37

Subtask: 2

Verdict: ACCEPTED

input
`110011001100110011001100101010...` view save

correct output
`QAQ` view save

user output
`QAQ` view save

Test 38

Subtask: 2

Verdict: WRONG ANSWER

input
`110011001100110011001100110011...` view save

correct output
`31 1 20 20 20 20 20 20 20 20 20 2...` view save

user output
`QAQ` view save

Test 39

Subtask: 2

Verdict: ACCEPTED

input
`010101010101010101010101010101...` view save

correct output
`48 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

user output
`48 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

Test 40

Subtask: 2

Verdict: WRONG ANSWER

input
`011010000011111011110000110011...` view save

correct output
`23 13 13 12 11 11 11 11 10 9 9 9 ...` view save

user output
`QAQ` view save

Test 41

Subtask: 3

Verdict: ACCEPTED

input
`0010101000` view save

correct output
`QAQ` view save

user output
`QAQ` view save

Test 42

Subtask: 3

Verdict: WRONG ANSWER

input
`0100010110` view save

correct output
`4 2 1 1 1` view save

user output
`QAQ` view save

Test 43

Subtask: 3

Verdict: WRONG ANSWER

input
`0100110110` view save

correct output
`4 2 1 1 1` view save

user output
`QAQ` view save

Test 44

Subtask: 3

Verdict: ACCEPTED

input
`1110000001` view save

correct output
`2 2 1` view save

user output
`2 2 1` view save

Test 45

Subtask: 3

Verdict: WRONG ANSWER

input
`0001001110` view save

correct output
`3 2 2 1` view save

user output
`QAQ` view save

Test 46

Subtask: 3

Verdict: ACCEPTED

input
`0011100011` view save

correct output
`3 1 2 1` view save

user output
`4 1 1 1 1` view save

Test 47

Subtask: 3

Verdict: ACCEPTED

input
`0100111100` view save

correct output
`3 1 1 1` view save

user output
`3 1 1 1` view save

Test 48

Subtask: 3

Verdict: ACCEPTED

input
`0001001000` view save

correct output
`3 2 2 1` view save

user output
`4 1 1 1 1` view save

Test 49

Subtask: 3

Verdict: WRONG ANSWER

input
`0100100010` view save

correct output
`4 2 1 1 1` view save

user output
`QAQ` view save

Test 50

Subtask: 3

Verdict: ACCEPTED

input
`1100101110` view save

correct output
`4 2 1 1 1` view save

user output
`4 3 3 2 1` view save

Test 51

Subtask: 3

Verdict: WRONG ANSWER

input
`1000111011` view save

correct output
`3 2 1 1` view save

user output
`QAQ` view save

Test 52

Subtask: 3

Verdict: ACCEPTED

input
`1000111111` view save

correct output
`2 1 1` view save

user output
`2 1 1` view save

Test 53

Subtask: 3

Verdict: ACCEPTED

input
`0110011100` view save

correct output
`3 2 1 1` view save

user output
`4 1 1 1 1` view save

Test 54

Subtask: 3

Verdict: WRONG ANSWER

input
`0001000110` view save

correct output
`3 2 2 1` view save

user output
`QAQ` view save

Test 55

Subtask: 3

Verdict: ACCEPTED

input
`1110110010` view save

correct output
`4 1 2 1 1` view save

user output
`4 3 2 2 1` view save

Test 56

Subtask: 3

Verdict: ACCEPTED

input
`110011001100110011001100110011...` view save

correct output
`QAQ` view save

user output
`QAQ` view save

Test 57

Subtask: 3

Verdict: ACCEPTED

input
`110011001100110011001100110011...` view save

correct output
`QAQ` view save

user output
`QAQ` view save

Test 58

Subtask: 3

Verdict: WRONG ANSWER

input
`110011001100110011001100110011...` view save

correct output
`1501 1 1000 1000 1000 1000 1000 100...` view save

user output
`QAQ` view save

Test 59

Subtask: 3

Verdict: ACCEPTED

input
`010101010101010101010101010101...` view save

correct output
`2498 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

user output
`2498 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

Test 60

Subtask: 3

Verdict: WRONG ANSWER

input
`011100011001011111111000010110...` view save

correct output
`1272 1 1 648 647 646 646 645 645 64...` view save

user output
`QAQ` view save

Test 61

Subtask: 4

Verdict: ACCEPTED

input
`1110101110` view save

correct output
`QAQ` view save

user output
`QAQ` view save

Test 62

Subtask: 4

Verdict: ACCEPTED

input
`0111001011` view save

correct output
`4 2 1 1 1` view save

user output
`4 3 2 1 1` view save

Test 63

Subtask: 4

Verdict: ACCEPTED

input
`1101111101` view save

correct output
`3 2 2 1` view save

user output
`3 2 2 1` view save

Test 64

Subtask: 4

Verdict: WRONG ANSWER

input
`1001110001` view save

correct output
`3 2 1 1` view save

user output
`QAQ` view save

Test 65

Subtask: 4

Verdict: ACCEPTED

input
`1000000011` view save

correct output
`2 1 1` view save

user output
`2 1 1` view save

Test 66

Subtask: 4

Verdict: ACCEPTED

input
`0100010111` view save

correct output
`4 1 1 1 1` view save

user output
`4 1 1 1 1` view save

Test 67

Subtask: 4

Verdict: ACCEPTED

input
`0100111010` view save

correct output
`4 2 1 1 1` view save

user output
`4 2 1 1 1` view save

Test 68

Subtask: 4

Verdict: ACCEPTED

input
`0010111101` view save

correct output
`4 1 1 1 1` view save

user output
`4 1 1 1 1` view save

Test 69

Subtask: 4

Verdict: ACCEPTED

input
`0011111000` view save

correct output
`2 2 1` view save

user output
`3 1 1 1` view save

Test 70

Subtask: 4

Verdict: WRONG ANSWER

input
`1101001101` view save

correct output
`4 2 2 2 1` view save

user output
`QAQ` view save

Test 71

Subtask: 4

Verdict: ACCEPTED

input
`0110111000` view save

correct output
`3 2 1 1` view save

user output
`4 1 1 1 1` view save

Test 72

Subtask: 4

Verdict: ACCEPTED

input
`1100110111` view save

correct output
`3 3 2 1` view save

user output
`4 4 3 2 1` view save

Test 73

Subtask: 4

Verdict: ACCEPTED

input
`1110011111` view save

correct output
`2 2 1` view save

user output
`3 1 1 1` view save

Test 74

Subtask: 4

Verdict: ACCEPTED

input
`1011000101` view save

correct output
`4 2 1 1 1` view save

user output
`4 2 1 1 1` view save

Test 75

Subtask: 4

Verdict: ACCEPTED

input
`1110110010` view save

correct output
`4 1 2 1 1` view save

user output
`4 3 2 2 1` view save

Test 76

Subtask: 4

Verdict: ACCEPTED

input
`110011001100110011001100110011...` view save

correct output
`QAQ` view save

user output
`QAQ` view save

Test 77

Subtask: 4

Verdict: ACCEPTED

input
`110011001100110011001100110011...` view save

correct output
`QAQ` view save

user output
`QAQ` view save

Test 78

Subtask: 4

Verdict: WRONG ANSWER

input
`110011001100110011001100110011...` view save

correct output
`30001 1 20000 20000 20000 20000 2000...` view save

user output
`QAQ` view save

Test 79

Subtask: 4

Verdict: TIME LIMIT EXCEEDED

input
`010101010101010101010101010101...` view save

correct output
`49998 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

user output
(empty)

Test 80

Subtask: 4

Verdict: ACCEPTED

input
`111000110000011000001101010010...` view save

correct output
`25011 1 12471 12470 12469 12468 1246...` view save

user output
`33315 25005 25004 25003 25002 25001 ...` view save