CSES - Datatähti 2022 alku - Results
Submission details
Task:Ositus
Sender:shmoul
Submission time:2021-10-16 16:01:38 +0300
Language:C++ (C++17)
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.03 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 'int calculate2(std::__cxx11::string)':
input/code.cpp:39: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[i]=true;
		for(;j<s.length();j++)
		{
			if(Visited[s[j]])
			{
				pair<int, int> RangeContainsCut = {i, j};
				CutRanges.push_back(RangeContainsCut);
				break;
			}
			Visited[s[i]] = true;
		}
		Visited.reset();
	}
	return CutRanges;
}
int calculate2(string s)
{
	string temp = s;
	vector<pair<int, int>> CutRanges = GetCutRanges(s);
	list<int> OverlapLengths;
	int answer=1;
	int Multiplier = pow(2, s.length()-1-CutRanges.back().second);

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

Test details

Test 1

Group: 1, 2, 3

Verdict:

input
a

correct output
1

user output
(empty)

Test 2

Group: 1, 2, 3

Verdict:

input
abcdefghij

correct output
512

user output
(empty)

Test 3

Group: 1, 2, 3

Verdict:

input
abcabaacbc

correct output
120

user output
8212

Test 4

Group: 1, 2, 3

Verdict:

input
aaxxxxxxaa

correct output
4

user output
524392

Test 5

Group: 2, 3

Verdict:

input
mfyzvoxmppoxcvktmcjkryyocfweub...

correct output
643221148

user output
11480

Test 6

Group: 3

Verdict:

input
weinscqmmpgbrlboocvtbptgbahmwv...

correct output
831644159

user output
(empty)

Error:
free(): invalid pointer

Test 7

Group: 3

Verdict:

input
sxaoxcyrjoeieyinaqxwukgzdnhhsw...

correct output
816016015

user output
(empty)

Error:
free(): invalid pointer