Well... I tried first to solve this problem in Java, but it resulted in TLE 15, without any visible reason.

But assuming that this is Java and I'm not an expert in it, this may be...

The same algorithm in C++(copy-paste with apropriate changes) passes 15th test, but receives a MLE on 20th test.

My imagination can't help me to find what's the reason.
All my tests can't make my program use more than 2MB of memory. I tried even more than 100KB of input in different configurations(a lot of small strings or a few of long ones,same and different, with different percent of numbers), but result is the same. What can be the test that my program uses more than 80MB???

If you think that this is because of my bad code...here it is:

#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
class Character
{
public:
    static bool isDigit(char c)
    {
        return c>='0' && c<='9';
    }
};
class FastJapstring
{
public:
        string data;

        FastJapstring(string &data) {
            this->data = data;
        }
         static int skipZeroz(string &s,int from,int l)
        {
            for(int i = from; i <l;i++)
                if(s[i]!='0')return i;
            return l;
        }
         static int findNotNumber(string &s,int from,int l)
        {
            for(int i = from; i <l;i++)
                if(!(s[i]<='9' && s[i]>='0'))return i;
            return l;

        }
         static int cmpNumParts(string& fs,int ffrom,int fto, string& ss,int sfrom,int sto)
        {
            int fln = fto-ffrom;
            int sln = sto-sfrom;
            if(fln!=sln)return fln-sln;
            for(int i =0; i < fln; i++)
            {
                if(fs[ffrom+i]!=ss[sfrom+i])
                    return (int)fs[ffrom+i] - (int)ss[sfrom+i];
            }
            return 0;
        }
         static int findNotLetter(string& s,int from,int l)
        {
               for(int i = from; i <l;i++)
                if(s[i]>='0'&&s[i]<='9')return i;
            return l;
        }
         static int cmpStrParts(string& fs,int ffrom,int fto, string& ss,int sfrom,int sto)
        {
            int fln = fto-ffrom;
            int sln = sto-sfrom;

            for(int i =0; i < min(fln,sln); i++)
            {
                if(fs[ffrom+i]!=ss[sfrom+i])
                    return (int)fs[ffrom+i] - (int)ss[sfrom+i];
            }
            if(fln!=sln)return fln-sln;
            return 0;
        }

         int compare_to (FastJapstring &o)
         {
            string& f = data;
            string& s = o.data;
            int fi,si;
            if(Character::isDigit(f[0]))
                fi=0;
            else fi=1;
            if(Character::isDigit(s[0]))si=0;
            else si=1;

            if(fi!=si)return fi - si;
            int fl = f.length();
            int sl = s.length();
            int zeroDominate=0;
            if(fi==0)
            {
                fi=si=0;
                while(true)
                 {
                    int res;
                    int fzeroZ = fi;
                    int DigStart = skipZeroz(f, fi, fl);
                    fzeroZ = DigStart - fi;
                    int DigEndPlus = findNotNumber(f, DigStart, fl);
                    int szeroZ = si;
                    int DigStart1 = skipZeroz(s, si, sl);
                    szeroZ = DigStart1-si;
                    if(zeroDominate==0)zeroDominate = fzeroZ - szeroZ;

                    int DigEndPlus1 = findNotNumber(s, DigStart1, sl);
                    res  = cmpNumParts(f, DigStart, DigEndPlus, s, DigStart1, DigEndPlus1);
                    if(res!=0)return res;
                    fi = DigEndPlus;
                    si = DigEndPlus1;
                    if(fi>=fl && si >=sl)break;
                    if(fi>=fl)return -1;
                    if(si>=sl)return 1;

                    int fLetterEndPlus = findNotLetter(f, fi, fl);
                    int sLetterEndPlus = findNotLetter(s, si, sl);
                    res = cmpStrParts(f, fi, fLetterEndPlus, s, si, sLetterEndPlus);
                    if(res!=0)return res;
                    fi = fLetterEndPlus;
                    si = sLetterEndPlus;
                    if(fi>=fl && si >=sl)break;
                    if(fi>=fl)return -1;
                    if(si>=sl)return 1;

                }
            }
            else
            {
                fi=si=0;
                while(true)
                 {
                    int res;
                    int fLetterEndPlus = findNotLetter(f, fi, fl);
                    int sLetterEndPlus = findNotLetter(s, si, sl);
                    res = cmpStrParts(f, fi, fLetterEndPlus, s, si, sLetterEndPlus);
                    if(res!=0)return res;
                    fi = fLetterEndPlus;
                    si = sLetterEndPlus;
                    if(fi>=fl && si >=sl)break;
                    if(fi>=fl)return -1;
                    if(si>=sl)return 1;


                    int fzeroZ = fi;
                    int DigStart = skipZeroz(f, fi, fl);
                    fzeroZ = DigStart - fi;
                    int DigEndPlus = findNotNumber(f, DigStart, fl);
                    int szeroZ = si;
                    int DigStart1 = skipZeroz(s, si, sl);
                    szeroZ = DigStart1-si;
                    if(zeroDominate==0)zeroDominate = fzeroZ - szeroZ;
                    int DigEndPlus1 = findNotNumber(s, DigStart1, sl);
                    res  = cmpNumParts(f, DigStart, DigEndPlus, s, DigStart1, DigEndPlus1);
                    if(res!=0)return res;
                    fi = DigEndPlus;
                    si = DigEndPlus1;
                    if(fi>=fl && si >=sl)break;
                    if(fi>=fl)return -1;
                    if(si>=sl)return 1;

                }
            }
            return -zeroDominate;


        }
      bool operator < (FastJapstring &o)
      {
          return compare_to(o)<0;
      }

};


int main()
{
l:
    string s;
    vector<FastJapstring> data;
    //freopen("in.txt","r",stdin);
    while(getline(cin,s))
    {
        if(s=="d")break;
        if(s.empty())continue;
        data.push_back(FastJapstring(s));
    }
    sort(data.begin(),data.end());

    for(int i = 0; i < data.size();i++)
    {
        cout << data[i].data << endl;
    }
    //goto l;
    return 0;
}

I had a same problem.
Try not to keep the string in class. When you sort, C++ copies objects and eats all memory.
When I store all strings in global array, I recived AC with 3MB memory.
Also you can try to sort vector of indexes

Edited by author 29.04.2011 12:26