10226 - Hardwood Species

[robin_0]

I'm getting TLE
Would anybody kindly see what may be wrong here :/
I modified merge sort algorithm to get nlogn time but instead I'm getting TLE :/

Code: Select all

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

char L[20005][50],R[20005][50],array[20005][50];
int cnt[20005],lc[20005],rc[20005];

void mergesort(int p,int r);
void merge (int p ,int q ,int r);

void mergesort(int p,int r)
{
    if(p<r)
    {
        int q=(p+r)/2;
        mergesort(p,q);
        mergesort(q+1,r);
        merge(p,q,r);
    }

}

void merge (int p ,int q ,int r)
{

    int n1=q-p+1;
    int n2=r-q;
    int i,j,k;

    for(i=0;i<n1;i++)
    {
        strcpy(L[i],array[i+p]);
        lc[i]=cnt[i+p];
    }


    for(j=0;j<n2;j++)
    {

        strcpy(R[j],array[j+q+1]);
        rc[j]=cnt[j+q+1];
    }

    i=0;
    j=0;

    for(k=p;k<=r;k++)
    {
       if(i<n1&&j<n2)
       {
           if(strcmp(L[i],R[j])<0)
           {
               strcpy(array[k],L[i]);
               cnt[k]=lc[i];
               i++;
           }
           else
           {
               strcpy(array[k],R[j]);
               cnt[k]=rc[j];
               j++;
           }

       }
       else if(i<n1)
       {

                strcpy(array[k],L[i]);
                cnt[k]=lc[i];
                i++;

       }
       else
       {
                strcpy(array[k],R[j]);
                cnt[k]=rc[j];
                j++;
       }
    }
}

int main()
{
    int t,i,j,tot=0,tp=1,sum;
    char inp[200];

    scanf("%d",&t);
    gets(array[0]);
    gets(array[0]);

    for(;tp<=t;tp++)
    {
        if(tp>1)
            printf("\n");
        sum=0;
        tot=0;
        while(gets(inp))
        {
            if(strlen(inp)==0)
                break;
            sum++;
            for(i=0;i<tot;i++)
            {
                if(!strcmp(inp,array[i]))
                {
                    {
                        cnt[i]++;
                        break;
                    }
                }
            }
            if(i==tot)
            {
                strcpy(array[tot],inp);
                cnt[tot]=1;
                tot++;
            }
        }

        mergesort(0,tot-1);

        for(i=0;i<tot;i++)
            printf("%s %.4lf\n",array[i],((double)cnt[i]/(double)sum)*100.00);
    }


    return 0;
}

[bappi48]

Please can anyone indicate where I'm doing wrong. On sample input output I'm getting correct answer, but in Online judge I'm getting WA.

Code: Select all

#include <iostream>
#include <set>
#include <map>
#include <iomanip>
#include <sstream>

#include <cstdio>

using namespace std;

int main()
{
    
    set<string> treeSet;
    set<string>::iterator it;
    map<string,int> treeCount;

    string tmpString;
    int caseCount,totalTrees;
    float percentage;

    cin>>caseCount>>ws;

    for(int i=0;i<caseCount;i++){
        totalTrees = 0;
        treeSet.clear();
        treeCount.clear();
        while(1){ // Read all string in testSet
            getline(cin,tmpString);
            if(tmpString == "") break;
            treeSet.insert(tmpString);
            treeCount[tmpString]++;
            totalTrees++;
        }

        for(it = treeSet.begin(); it!=treeSet.end();it++){
            percentage = (treeCount[*it] * 100.00 )/totalTrees ;
            cout<<*it<<" "<<fixed<<setprecision(4)<<percentage<<endl;
        }

        if((i+1)<caseCount){
            cout<<'\n';
        }


    }



    return 0;
}