CSES - DatatÃ¤hti 2022 alku - Results
 Task: Ositus 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)

for (int i = 0; i < amount; i++) {
for (int j = 0; j < input.indexOf(character); j++) {
for (char c : blacklist) {
if (c == input.charAt(j)) {
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);
}
}
} 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);
}*/

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--;
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--;
nextCharIndex = characterIndex + i;
break;
}
// b:a:b     (original idea)
else {
//System.out.println("Found before: " + lastCharI[in.charAt(characterIndex + i) - 97]);
// default
long v = 1;
for (int k = 0; k < i; k++) {
v *= 2;
while (v >= 1000000007) {
v -= 1000000007;
}
} //   v = 2^i
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
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
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--;
nextCharIndex = lastIndex + 1;
break;
}
}
}
characterIndex = nextCharIndex;
}
}
}

### 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

Group: 1, 2, 3

Verdict:

input
abcabaacbc

correct output
120

user output
82

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)