| Task: | Ositus |
| Sender: | mbezirgan |
| Submission time: | 2021-10-14 23:39:10 +0300 |
| Language: | C++ (C++17) |
| Status: | READY |
| Result: | 40 |
| group | verdict | score |
|---|---|---|
| #1 | ACCEPTED | 40 |
| #2 | WRONG ANSWER | 0 |
| #3 | WRONG ANSWER | 0 |
| test | verdict | time | group | |
|---|---|---|---|---|
| #1 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
| #2 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
| #3 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
| #4 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
| #5 | WRONG ANSWER | 0.01 s | 2, 3 | details |
| #6 | WRONG ANSWER | 0.04 s | 3 | details |
| #7 | TIME LIMIT EXCEEDED | -- | 3 | details |
Code
#include <iostream>
#include <cmath>
#include <vector>
int main()
{
std::string s;
std::cin >> s;
struct Multiplication
{
uint64_t left, right;
};
std::vector<Multiplication> Multiplications;
for (uint64_t i = 0; i < s.size(); i++)
{
bool letters[26] = {};
letters[s[i] - 'a'] = true;
for (uint64_t j = i + 1; j < s.size(); j++)
{
if (letters[s[j] - 'a'])
break;
Multiplications.push_back({ i, j });
letters[s[j] - 'a'] = true;
}
}
// How many combinations of multiplications can be put inside of the given range. First 2 numbers aren't needed but I'm too lazy to optimize it
uint64_t* combinations = new uint64_t[s.size()]();
for (uint64_t i = 0; i < Multiplications.size(); i++)
{
uint64_t lastTotal = 0;
if (Multiplications[i].left)
{
for (int j = Multiplications[i].left - 1; j != 0; j--)
{
lastTotal += combinations[j];
}
}
combinations[Multiplications[i].right] += 1 + lastTotal;
combinations[Multiplications[i].right] = combinations[Multiplications[i].right] % 1000000007;
}
uint64_t count = 1;
for (uint64_t i = 1; i < s.size(); i++)
{
count += combinations[i];
}
std::cout << count;
}
/*
EXAMPLES FOR TESTING
A B A C
A B AC
A BA C
A BAC
AB A C
AB AC
A Y B A
A Y BA
A YB A
A YBA
AY B A
AY BA
AYB A
A Y B A B 1
A Y B AB 2
A Y BA B 3
A YB A B 4
A YB AB 5
A YBA B 6
AY B A B 7
AY B AB 8
AY BA B 9
AYB A B 10
AYB AB 11
*/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: ACCEPTED
| input |
|---|
| abcabaacbc |
| correct output |
|---|
| 120 |
| user output |
|---|
| 120 |
Test 4
Group: 1, 2, 3
Verdict: ACCEPTED
| input |
|---|
| aaxxxxxxaa |
| correct output |
|---|
| 4 |
| user output |
|---|
| 4 |
Test 5
Group: 2, 3
Verdict: WRONG ANSWER
| input |
|---|
| mfyzvoxmppoxcvktmcjkryyocfweub... |
| correct output |
|---|
| 643221148 |
| user output |
|---|
| 31643221365 |
Test 6
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| weinscqmmpgbrlboocvtbptgbahmwv... |
| correct output |
|---|
| 831644159 |
| user output |
|---|
| 2421831661106 |
Test 7
Group: 3
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| sxaoxcyrjoeieyinaqxwukgzdnhhsw... |
| correct output |
|---|
| 816016015 |
| user output |
|---|
| (empty) |
