CSES - Datatähti 2022 alku - Results
Submission details
Task:Ositus (Partitioning)
Sender:jmarttinen
Submission time:2021-10-05 08:51:48
Language:C++11
Status:READY
Result:40
Feedback
groupverdictscore
#1ACCEPTED40
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#4ACCEPTED0.01 s1, 2, 3details
#5--2, 3details
#6--3details
#70.32 s3details

Compiler report

input/code.cpp: In function 'long long int f(std::__cxx11::string)':
input/code.cpp:37:55: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (lookupTable.size() < MAXTABLESIZE && s.size() < n * 1 / 10)
                                              ~~~~~~~~~^~~~~~~~~~~~

Code

#include <algorithm>
#include <map>
#include <iostream>
#include <set>
#include <string> 


using namespace std;

unsigned int MAXTABLESIZE = 1e3;
long M = 1e9 + 7;
int n;

map<string, long long> lookupTable;

long long f(string s) {
    string substr, tail;
    long v = 0;
    if (s.size() <= 1) {
        return 1;
    } else if (s.size() == 2) {
        return 1 + (s[0] != s[1]);
    }
    if (lookupTable.count(s)) {
        return lookupTable[s];
    }
    // int i = find(s.rend()-1, s.rbegin(), s[s.size()-1]);

    for (unsigned int i=1; i<=s.size(); i++) {
        substr = s.substr(0, s.size()-i), tail = s.substr(s.size()-i, i);

        if (set<char>(tail.begin(), tail.end()).size() != tail.size())
            break;
        v += f(substr);
        v %= M;
    }
    if (lookupTable.size() < MAXTABLESIZE && s.size() < n * 1 / 10)
        lookupTable[s] = v;
    return v;

}


int main() {
    string s;

    cin >> s;
    n = s.size();
    cout << f(s);

}

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:

input
mfyzvoxmppoxcvktmcjkryyocfweub...

correct output
643221148

user output
(empty)

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)