ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1546. Japanese Sorting

strange memory limit C++???
Posted by messir 27 Aug 2010 15:02
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;
}
Re: strange memory limit C++???
Posted by Erop [USU] 29 Apr 2011 02:46
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