| Task: | Ositus |
| Sender: | Zendium |
| Submission time: | 2021-10-16 21:07:35 +0300 |
| Language: | Java |
| Status: | READY |
| Result: | 0 |
| group | verdict | score |
|---|---|---|
| #1 | WRONG ANSWER | 0 |
| #2 | WRONG ANSWER | 0 |
| #3 | WRONG ANSWER | 0 |
| test | verdict | time | group | |
|---|---|---|---|---|
| #1 | ACCEPTED | 0.13 s | 1, 2, 3 | details |
| #2 | ACCEPTED | 0.13 s | 1, 2, 3 | details |
| #3 | WRONG ANSWER | 0.12 s | 1, 2, 3 | details |
| #4 | WRONG ANSWER | 0.13 s | 1, 2, 3 | details |
| #5 | WRONG ANSWER | 0.47 s | 2, 3 | details |
| #6 | TIME LIMIT EXCEEDED | -- | 3 | details |
| #7 | TIME LIMIT EXCEEDED | -- | 3 | details |
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: WRONG ANSWER
| input |
|---|
| abcabaacbc |
| correct output |
|---|
| 120 |
| user output |
|---|
| 82 |
Test 4
Group: 1, 2, 3
Verdict: WRONG ANSWER
| input |
|---|
| aaxxxxxxaa |
| correct output |
|---|
| 4 |
| user output |
|---|
| 3 |
Test 5
Group: 2, 3
Verdict: WRONG ANSWER
| input |
|---|
| mfyzvoxmppoxcvktmcjkryyocfweub... |
| correct output |
|---|
| 643221148 |
| user output |
|---|
| -227119187 |
Test 6
Group: 3
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| weinscqmmpgbrlboocvtbptgbahmwv... |
| correct output |
|---|
| 831644159 |
| user output |
|---|
| (empty) |
Test 7
Group: 3
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| sxaoxcyrjoeieyinaqxwukgzdnhhsw... |
| correct output |
|---|
| 816016015 |
| user output |
|---|
| (empty) |