CSES - Datatähti 2022 alku - Results
Submission details
Task:Ositus (Partitioning)
Sender:Zendium
Submission time:2021-10-16 21:07:35
Language:Java
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.13 s1, 2, 3details
#2ACCEPTED0.13 s1, 2, 3details
#30.12 s1, 2, 3details
#40.13 s1, 2, 3details
#50.47 s2, 3details
#6--3details
#7--3details

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class NeljasEhka {
    public static String in;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Sum *= (v(b:a)-1)*(v(a:b)) + (v(a:b) - 1)
        // Sum++;
        // Sum /= v(b:a)

        //          sum *= v(a:b) - 1
        //          sum += oldsum - m

        /*
                       to get m:
                       func(boolean[26] isInEnd, indexOf b)



         */

        //          7 *1 + (7-)

        //           (7*(2+1)+1)/2 *4
        //           7 *(2+1) +1 /2 *4
        //          isajdajaoid
        //          31 *7 +1 /4 *3 +1 /2 *(127*4 + 3) +1 /128 *63 +1 /32
        in = scanner.nextLine();
        System.out.println(sumUntil(new boolean[26], in.length() - 1));
    }
            /*
            if (!skip) {
                String input = in;

                int amount = ((input.charAt(0) == character)?1:0)+((input.charAt(input.length()-1) == character)?1:0);
                amount += input.split(String.valueOf(character)).length - 2;

                if (amount > 1)
                    blacklist.add(character);

                for (int i = 0; i < amount; i++) {
                    int lastBadCharIndex = 0;
                    for (int j = 0; j < input.indexOf(character); j++) {
                        for (char c : blacklist) {
                            if (c == input.charAt(j)) {
                                lastBadCharIndex = j;
                                //System.out.println("bad: " + input.charAt(lastBadCharIndex));
                                break;
                            }
                        }
                    }

                    int beforelength = input.indexOf(character) - lastBadCharIndex;
                    if (input.indexOf(character) - 1 <= lastBadCharIndex) beforelength+=1;z
                    //System.out.println(beforelength);
                    input = input.substring(input.indexOf(character) + 1);
                    //System.out.println(input);
                    int afterLength = input.length() - ((input.contains(""+character))?input.indexOf(character):input.length());
                    //System.out.println(afterLength);
                    answer+= (long) afterLength *beforelength;
                    //System.out.println("Ans " + answer);
                    while (answer >= 1000000007) {
                        answer -= 1000000007;
                    }
                }
            } else {
                //System.out.println("Skip");
            }

             */

    //static int testloops = 0;
    public static long sumUntil(boolean[] belongsToLast, int lastIndex) {

        //System.out.println("new");
        /*testloops++;
        if (testloops > 10) {
            System.exit(69);
        }*/

        long answer = 1;
        int[] lastCharI = new int[26];
        Arrays.fill(lastCharI, -1);

        for (int characterIndex = 0; characterIndex <= lastIndex; characterIndex += 0) {
            //System.out.println("Character: " + in.charAt(characterIndex) + " index: " + characterIndex);
            int nextCharIndex = 0;
            for (int i = 0; i < 27; i++) {
                //System.out.println("i = " + i);
                if (characterIndex + i <= lastIndex) {
                    if (i != 0) {
                        if (lastCharI[in.charAt(characterIndex + i) - 97] == -1) {
                            //System.out.println("Unseen before");
                            lastCharI[in.charAt(characterIndex + i) - 97] = characterIndex + i;
                        } else {
                            //System.out.print("Found: " + in.charAt(characterIndex + i) + " " + characterIndex + i + ", ");
                            // a:b:b
                            if (lastCharI[in.charAt(characterIndex + i) - 97] > characterIndex) {
                                //System.out.println("Seen after");
                                int ab0 = lastCharI[in.charAt(characterIndex + i) - 97] - characterIndex;
                                long v = 1;
                                for (int k = 0; k < ab0; k++) {
                                    v *= 2;
                                    while (v >= 1000000007) {
                                        v -= 1000000007;
                                    }
                                } //   v = 2^ab0
                                int b0b1 = characterIndex + i - lastCharI[in.charAt(characterIndex + i) - 97];
                                long v1 = 1;
                                for (int k = 0; k < b0b1; k++) {
                                    v1 *= 2;
                                    while (v1 >= 1000000007) {
                                        v1 -= 1000000007;
                                    }
                                } //   v1 = 2^b0b1
                                v1--;
                                answer *= v * v1;
                                nextCharIndex = characterIndex + i;
                                break;
                            }
                            // a:a
                            else if (lastCharI[in.charAt(characterIndex + i) - 97] == characterIndex) {
                                //System.out.println("Found Same");
                                // v(a0:a1) - 1 kai
                                long v = 1;
                                for (int k = 0; k < i; k++) {
                                    v *= 2;
                                    while (v >= 1000000007) {
                                        v -= 1000000007;
                                    }
                                } //   v = 2^i
                                v--;
                                answer *= v;
                                nextCharIndex = characterIndex + i;
                                break;
                            }
                            // b:a:b     (original idea)
                            else {
                                //System.out.println("Found before: " + lastCharI[in.charAt(characterIndex + i) - 97]);
                                // default
                                long oldansw = answer;
                                long v = 1;
                                for (int k = 0; k < i; k++) {
                                    v *= 2;
                                    while (v >= 1000000007) {
                                        v -= 1000000007;
                                    }
                                } //   v = 2^i
                                v--;
                                answer *= v;
                                boolean[] x = new boolean[26];
                                for (int ind = lastCharI[in.charAt(characterIndex + i) - 97]; ind <= characterIndex; ind++) {
                                    x[in.charAt(ind) - 97] = true;
                                }
                                if (lastCharI[in.charAt(characterIndex + i) - 97] != 0)
                                    answer += oldansw - sumUntil(x, lastCharI[in.charAt(characterIndex + i) - 97]);
                                else
                                    answer += oldansw - 1;
                                nextCharIndex = characterIndex + i;
                                break;
                            }

                        }
                    } else {
                        lastCharI[in.charAt(characterIndex + i) - 97] = characterIndex + i;
                    }
                } else {
                    //System.out.println("Out of bounds");
                    int lastCharIndex = characterIndex + i - 1;
                    int cutoffIndex = -1;
                    for (int ind = lastCharIndex; ind > characterIndex - 1; ind--) {
                        if (belongsToLast[in.charAt(ind) - 97] && ind != lastCharIndex) {
                            cutoffIndex = ind;
                            break;
                        }
                    }
                    //System.out.println("Cutoff: " + cutoffIndex);
                    if (cutoffIndex == -1) {
                        long v = 1;
                        for (int k = 0; k < i-1; k++) {v *= 2;while (v >= 1000000007){v -= 1000000007;}} //   v = 2^i-1
                        answer*=v;
                        nextCharIndex = lastIndex+1;
                        break;
                    } else {
                        int ab0 = cutoffIndex - characterIndex;
                        long v = 1;
                        for (int k = 0; k < ab0; k++) {v *= 2;while (v >= 1000000007){v -= 1000000007;}} //   v = 2^ab0
                        int b0b1 = lastCharIndex - cutoffIndex;
                        long v1 = 1;
                        for (int k = 0; k < b0b1; k++) {v1 *= 2;while (v1 >= 1000000007){v1 -= 1000000007;}} //   v1 = 2^b0b1
                        v1--;
                        answer *= v*v1;
                        nextCharIndex = lastIndex + 1;
                        break;
                    }
                }
            }
            characterIndex = nextCharIndex;
            answer = answer % 1000000007;
            //System.out.println(answer);
        }
        return answer;
    }
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
a

correct output
1

user output
1

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
abcdefghij

correct output
512

user output
512

Test 3

Group: 1, 2, 3

Verdict:

input
abcabaacbc

correct output
120

user output
82

Test 4

Group: 1, 2, 3

Verdict:

input
aaxxxxxxaa

correct output
4

user output
3

Test 5

Group: 2, 3

Verdict:

input
mfyzvoxmppoxcvktmcjkryyocfweub...

correct output
643221148

user output
-227119187

Test 6

Group: 3

Verdict:

input
weinscqmmpgbrlboocvtbptgbahmwv...

correct output
831644159

user output
(empty)

Test 7

Group: 3

Verdict:

input
sxaoxcyrjoeieyinaqxwukgzdnhhsw...

correct output
816016015

user output
(empty)