CSES - Datatähti 2022 alku - Results
Submission details
Task:Ositus
Sender:shmoul
Submission time:2021-10-16 16:08:38 +0300
Language:C++ (C++17)
Status:COMPILE ERROR

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: At global scope:
input/code.cpp:31:1: error: '__int64' does not name a type; did you mean '__rintf64'?
 __int64 calculate(string s)
 ^~~~~~~
 __rintf64
input/code.cpp: In function 'int main()':
input/code.cpp:67:8: error: 'calculate' was not declared in this scope
  cout<<calculate(s);
        ^~~~~~~~~

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;
}
__int64 calculate(string s)
{
	string temp = s;
	vector<pair<int, int>> CutRanges = GetCutRanges(s);
	list<int> OverlapLengths;
	__int64 answer=1;
	if(CutRanges.size()<1) return pow(2, s.length()-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+=__int64(i+1);
	}
	if(OverlapLengths.size()==0)
	{
		answer++;
	}
	answer*=Multiplier;
	//cout<<endl<<answer;
	return answer;
}
int main()
{
	string s;
	cin>>s;
	cout<<calculate(s);
	return 0;
}