Task: | Ositus |
Sender: | Zendium |
Submission time: | 2021-10-16 20:13:33 +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.12 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.12 s | 1, 2, 3 | details |
#3 | WRONG ANSWER | 0.12 s | 1, 2, 3 | details |
#4 | WRONG ANSWER | 0.12 s | 1, 2, 3 | details |
#5 | RUNTIME ERROR | 0.13 s | 2, 3 | details |
#6 | RUNTIME ERROR | 0.15 s | 3 | details |
#7 | RUNTIME ERROR | 0.33 s | 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[ind]) { cutoffIndex = ind; } } //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 |
---|
79 |
Test 4
Group: 1, 2, 3
Verdict: WRONG ANSWER
input |
---|
aaxxxxxxaa |
correct output |
---|
4 |
user output |
---|
3 |
Test 5
Group: 2, 3
Verdict: RUNTIME ERROR
input |
---|
mfyzvoxmppoxcvktmcjkryyocfweub... |
correct output |
---|
643221148 |
user output |
---|
(empty) |
Error:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 30 out of bounds for length 26 at NeljasEhka.sumUntil(NeljasEhka.java:177) at NeljasEhka.sumUntil(NeljasEhka.java:161) at NeljasEhka.main(NeljasEhka.java:34)
Test 6
Group: 3
Verdict: RUNTIME ERROR
input |
---|
weinscqmmpgbrlboocvtbptgbahmwv... |
correct output |
---|
831644159 |
user output |
---|
(empty) |
Error:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 27 out of bounds for length 26 at NeljasEhka.sumUntil(NeljasEhka.java:177) at NeljasEhka.sumUntil(NeljasEhka.java:161) at NeljasEhka.main(NeljasEhka.java:34)
Test 7
Group: 3
Verdict: RUNTIME ERROR
input |
---|
sxaoxcyrjoeieyinaqxwukgzdnhhsw... |
correct output |
---|
816016015 |
user output |
---|
(empty) |
Error:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 32 out of bounds for length 26 at NeljasEhka.sumUntil(NeljasEhka.java:177) at NeljasEhka.sumUntil(NeljasEhka.java:161) at NeljasEhka.main(NeljasEhka.java:34)