CSES - Datatähti 2022 alku - Results
Submission details
Task:Ositus (Partitioning)
Sender:shmoul
Submission time:2021-10-17 19:44:49
Language:C++17
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#30.01 s1, 2, 3details
#4ACCEPTED0.01 s1, 2, 3details
#50.01 s2, 3details
#60.01 s3details
#70.08 s3details

Compiler report

input/code.cpp: In function 'std::vector<std::pair<int, int> > GetCutRanges(std::__cxx11::string)':
input/code.cpp:13:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s.length();i++)
              ~^~~~~~~~~~~
input/code.cpp:17:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(;j<s.length();j++)
        ~^~~~~~~~~~~
input/code.cpp: In function 'long long int calculate(std::__cxx11::string)':
input/code.cpp:43:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<CutRanges.size();i++)
              ~^~~~~~~~~~~~~~~~~
input/code.cpp:59:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<CutRanges.size();i++)
              ~^~~~~~~~~~~~~~~~~

Code

#include <iostream>
#include <map>
#include <list>
#include <bitset>
#include <vector>
#include <cmath>

using namespace std;
vector<pair<int, int>> GetCutRanges(string s)
{
	bitset<256> Visited;
	vector<pair<int, int>> CutRanges;
	for(int i=0;i<s.length();i++)
	{
		int j=i+1;
		Visited[s[i]]=true;
		for(;j<s.length();j++)
		{
			if(Visited[s[j]])
			{
				if(s[j]==s[i])
				{
					pair<int, int> RangeContainsCut = {i, j};
					CutRanges.push_back(RangeContainsCut);
				}
				break;
			}
			Visited[s[j]] = true;
		}
		Visited.reset();
	}
	return CutRanges;
}
long long calculate(string s)
{
	string temp = s;
	vector<pair<int, int>> CutRanges = GetCutRanges(s);
	list<int> OverlapLengths;
	long long answer = 1;
	if(CutRanges.size()<1) return pow(2, s.length()-1);
	int StartMultiplier = pow(2, CutRanges.front().first);
	int EndMultiplier = pow(2, s.length()-1-CutRanges.back().second);
	for(int i=0;i<CutRanges.size();i++)
	{
		pair<int,int> CurrentPair = CutRanges[i];
		//answer *= CurrentPair.second-CurrentPair.first;
		//cout<<answer<<endl<<CurrentPair.first<<"-"<<CurrentPair.second<<endl;

		int OverlapLength = 0;
		if(CurrentPair!=CutRanges.back() && CutRanges[i+1].first<CurrentPair.second)
		{
			OverlapLength = CurrentPair.second-CutRanges[i+1].first;
			//answer -= OverlapLength;
			OverlapLengths.push_back(OverlapLength);
		}
		answer = answer*pow(2,CurrentPair.second-OverlapLength-CurrentPair.first) - 1;
	}
	int NumNonSamePairs = 0;
	for(int i=0;i<CutRanges.size();i++)
	{
		pair<int,int> CurrentPair = CutRanges[i];
		if(CurrentPair!=CutRanges.back() && s[CutRanges[i].first]!=s[CutRanges[i+1].first])
		{
			NumNonSamePairs++;
		}
	}
	answer*=pow(2, NumNonSamePairs);
	answer*=StartMultiplier;
	answer*=EndMultiplier;
	answer/=OverlapLengths.size()+1;
	for(int i : OverlapLengths)
	{
		answer+=i-1;
	}
	//cout<<endl<<answer;
	return answer;
}
int main()
{
	string s;
	cin>>s;
	cout<<calculate(s);
	return 0;
}

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:

input
abcabaacbc

correct output
120

user output
222

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
11

Test 6

Group: 3

Verdict:

input
weinscqmmpgbrlboocvtbptgbahmwv...

correct output
831644159

user output
1014

Test 7

Group: 3

Verdict:

input
sxaoxcyrjoeieyinaqxwukgzdnhhsw...

correct output
816016015

user output
192470