CSES - Datatähti 2022 alku - Results
Submission details
Task:Ositus (Partitioning)
Sender:kpop
Submission time:2021-10-09 15:51:12
Language:C++11
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.01 s1, 2, 3details
#20.01 s1, 2, 3details
#30.01 s1, 2, 3details
#40.01 s1, 2, 3details
#50.01 s2, 3details
#60.01 s3details
#70.01 s3details

Code

#include <bits/stdc++.h>

using namespace std;

int main() {
  int result = 0;
  string s("aybabtu");// cin >> s;
  int n = s.length();
  vector<int> points(n, 0);
  unordered_set<char> seen;

  auto left = s.begin();
  auto right = left+1;

  while (left < s.end()) {
    int i = distance(s.begin(), right);

    if (seen.count(*right) == 0 && right != s.end()) {
      if (seen.empty()) seen.insert(*left);

      seen.insert(*right);
      ++points[i];
      ++right;
    } else {
      if (!seen.empty()) seen.clear();
      ++left;
      right = left+1;
    }
  }

  for (int i = 1; i < n; ++i) points[i] += points[i-1];

  seen.clear();
  left = s.begin();
  right = left+1;

  vector<int> finals(n, 0);

  while (left < s.end()) {
    int i = distance(s.begin(), left);
    int j = distance(s.begin(), right);

    if (seen.count(*right) == 0 && right != s.end()) {
      if (seen.empty()) seen.insert(*left);

      int p = 1;
      if (i>1) p += points[i-1];

      seen.insert(*right);
      finals[j] += p;
      ++right;
    } else {
      if (!seen.empty()) seen.clear();
      ++left;
      right = left+1;
    }
  }

  for (int i = 1; i < n; ++i) finals[i] += finals[i-1];

  seen.clear();
  
  for (int i = n-1; i > 0; --i) {
    char val = s[i];
    if (seen.count(val) != 0) break;

    int p = finals[i-1]+1;
    result += p;
    seen.insert(val);
  }

result+=1;

  cout << result%1000000007 << endl;
}

Test details

Test 1

Group: 1, 2, 3

Verdict:

input
a

correct output
1

user output
44

Test 2

Group: 1, 2, 3

Verdict:

input
abcdefghij

correct output
512

user output
44

Test 3

Group: 1, 2, 3

Verdict:

input
abcabaacbc

correct output
120

user output
44

Test 4

Group: 1, 2, 3

Verdict:

input
aaxxxxxxaa

correct output
4

user output
44

Test 5

Group: 2, 3

Verdict:

input
mfyzvoxmppoxcvktmcjkryyocfweub...

correct output
643221148

user output
44

Test 6

Group: 3

Verdict:

input
weinscqmmpgbrlboocvtbptgbahmwv...

correct output
831644159

user output
44

Test 7

Group: 3

Verdict:

input
sxaoxcyrjoeieyinaqxwukgzdnhhsw...

correct output
816016015

user output
44