Don't use int("smth"), because len of number can be greater than 4000 or use sys.set_int_max_str_digits() if you use python

Edited by author 26.07.2024 17:14

try to figure out how sorting in Japanese differs from regular sorting, there really isn’t such a big difference, but there will also be one trick with which you will need to suffer

We cannot imagine the test where our prog will give wrong answer!

does anybody know anything about WA on that test?

Уважаемые администраторы сайта!

Подскажите, пожалуйста, что Вы собираетесь делать с посылками, которые получали AC на компиляторе Intel C++ 7, и получают Time Limit на компиляторах G++ 4.7.2 и Visual C++ 2010?

У меня, например, около 4-5 таких задач было, пришлось все их перерешивать по-другому.
Ведь теперь нет возможности отправить задачу на старом компиляторе.

Извиняйте, но тогда нужно перетестировать посылки под Intel C++ 7 на новых компиляторах, а то результаты и рейтинг получаются НЕЧЕСТНЫМИ !!! Ведь не все перерешивают уже "сданные" задачи.

What the ***?

Edited by author 28.03.2013 22:52

It is "antiquicksort" test. Use pivot differ from (bottom + top) / 2, for example, random choosed.

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;
}

[code cut out]

Edited by author 11.05.2007 18:43

Test 3 contains equal values.

Edited by author 08.02.2009 22:43

is there any blank lines in an input file?

Is there any such pic name: "aa" or like "aa10bv10" ?

a001
a01
a
a0

=>

a
a0
a001
a01

[code deleted]

Edited by moderator 09.05.2007 16:03

photo01a45b
photo2a46b
photo02a5b

how to sot that?
or it cannot be such tests?

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
bool lesslength(const string& s1, const string& s2)
{
    return s1.length()<s2.length();
}
int main()
{
    string s;
    vector<string>a;
    while((cin>>s))

    {

        a.push_back(s);

    }
    stable_sort(a.begin(),a.end(),lesslength);
    vector<string>::iterator pos;
    for ( pos = a.begin(); pos != a.end(); ++pos)
    {
        cout<<*pos<<endl;
    }
    return 0;
}

I've WA 2.

I just want to know: there are only two types of photo's names(photoZ and photoxZ (where Z is some number)), or not?????????