Hashit

[lucckygeek]

i am getting tle in hashit https://www.spoj.pl/problems/HASHIT/
please tell if there is any problem with i/o if i am doing or any overflow of data type

#include<iostream>
#include<vector>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;
int num;
int has(string s)
{
	int size=s.size();
	int sum=0;
	for(int i=0;i<size;i++)
	{
		sum=sum+(int(s[i]))*(i+1);
    }
sum=sum*19;
int h=sum%101;
return (h);
}
int main()
{
	int t;
	scanf("%d",&t);
	for(int k=0;k<t;k++)
	{
		vector<string> v;
		vector<string> ve;
		for(int i=0;i<=101;i++)
		{
			v.push_back("0");
		}
		int n;
		scanf("%d",&n);
		num=n;
		string s1,s2;
		for(int j=0;j<n;j++)
		{
			cin>>s1;
			int d=s1.size();
			s2=s1.substr(4,d-4);
			int h=has(s2);
			if(s1[0]=='D')
			{
				int i=0;
				int index;		
				while(i<21)
				{
					index=(h+i*i+23*i)%101;
					if(v[index]=="0")
					{
						break;
					}
					if(v[index]==s2)
					{
						num--;
						v[index]="1";
						break;
					}
				}
				num--;
			}
			else if(s1[0]=='A')
			{
				int i=0;
				int index;
				//cout<<h<<endl;
				vector<string>::iterator it;
				it = find(ve.begin(),ve.end(),s2);
				if(it==ve.end())
				{
				while(i<20)
				{
					index=( h + i*i + 23*i )%101;
					if(v[index]=="0" || v[index]=="1")
					{
						v[index]=s2;
						//cout<<index<<"  "<<s2<<endl;
						ve.push_back(s2);
						break;
					}
					if(v[index]==s2)
					{
						num--;
						break;
					}
					i++;
				}}
				else
				{
					num--;
				}
			}
		}
		printf("%d\n",num);
		for(int i=0;i<101;i++)
		{
			if(v[i]!="0" && v[i]!="1")
			{
				cout<<i<<":"<<v[i]<<endl;
			}
		}
	}
	return 0;
}

[leppyr64]

Have you followed the definition in the problem statement? If yes, then you should have no issue with I/o.

Have you calculated the worst case of your calculations? If yes, do they exceed the data types? If no, then you should have no issues with overflow.

The complexity of find is O(n). You can do better using a different data structure.