вторник, 12 июня 2012 г.

Фуух...


Собственно, вот. Сделал одну из трёх. Вроде, время вышло, но никто не отключал меня ещё. Задачи сложные, скажу честно. Самую лёгкую решил, вот код:

Условие - первая на ссылке в предыдущем посте. Такой вот код у неё (695 строк):

#include <iostream>
#include <string>
#include <set>
#include <map>
using namespace std;

class vertex
{
    private:
        string name;
        unsigned long id;
        vertex* parent;
    public:
        map <unsigned long, vertex*>  childs;
        map < string, unsigned long > identifiers;

        vertex(vertex* _parent = NULL)
           :parent(_parent)
        {}

        vertex(unsigned long _id, vertex* _parent = NULL)
        :
            id(_id),
            parent(_parent)
        {}

        vertex(string _name, vertex* _parent = NULL)
        :
            name(_name),
            parent(_parent)
        {}

        vertex(string _name, unsigned long _id, vertex* _parent = NULL)
        :
            name(_name),
            id(_id),
            parent(_parent)
        {}

        bool operator <(const vertex& operand) const
        {
            return (GetId() < operand.GetId());
        }

        void SetName(const string& new_name)
        {
            name = new_name;
        }

        void SetId(const unsigned long& new_id)
        {
            id = new_id;
        }

        string GetName() const
        {
            return name;
        }

        unsigned long GetId() const
        {
            return id;
          }

          void AddChild(vertex* new_child)
          {
            new_child->SetParent(this);
         identifiers[new_child->GetName()] = new_child->GetId();
            childs[new_child->GetId()] = new_child;
        }

        vertex* NextChild(string _name)
        {
            return childs[ identifiers[_name] ];
        }

        void SetParent(vertex * _parent)
        {
            parent = _parent;
        }

        vertex* GetParent()
        {
            return parent;
        }
};

map < unsigned long, vertex* > vertexes;
       
class Dir
{
    private:
      string GetAttribute(string line, string attribute)
        {
            size_t pos = line.find(attribute, 0);
            pos += attribute.length();
           
            while (line[pos++] != '\'');
           
            size_t end = line.find('\'', pos);
            return string(line, pos, end-pos);
        }

        unsigned long StrToUnsignedLong(string s)
        {
            unsigned long ret = 0;
            for (int i = 0; i < s.length(); i++)
            {
                ret = ret*10UL + (unsigned long)(s[i]-'0');
            }

            return ret;
        }
        vertex *root;
        int size;
    public:

        void AddVertex(vertex* v)
        {
            vertexes[v->GetId()] = v;
        }

        vertex* GetVertexById(unsigned long id)
        {
            return vertexes[id];
        }

        void AddChild(vertex *parent, vertex* child)
        {
            AddVertex(child);
            parent->AddChild(child);
        }

        Dir()
        {
            root = NULL;
            size = 0;
        }

        int GetSize()
        {
            return size;
        }

        void SetSize(int new_size)
        {
            size = new_size;
        }

          void Read(string format)
        {
            if (format == "find")
            {
                ReadInFind();
            }
            if (format == "python")
            {
                ReadInPython();
           }
            if (format == "acm1")
            {
            ReadInAcm1();
            }
            if (format == "acm2")
            {
            ReadInAcm2();
            }
            if (format == "acm3")
            {
            ReadInAcm3();
            }
            if (format == "xml")
            {
                ReadInXML();
            }
        }

        void Write(string format)
        {
            if (format == "find")
            {
                WriteInFind(root);
            }
            if (format == "python")
            {
                WriteInPython(root);
           }
            if (format == "acm1")
            {
            WriteInAcm1();
            }
            if (format == "acm2")
            {
            WriteInAcm2();
            }
            if (format == "acm3")
            {
            WriteInAcm3();
            }
            if (format == "xml")
            {
                WriteInXML(root);
            }
        }

        void ReadInFind();
        void ReadInPython();
        void ReadInAcm1();
        void ReadInAcm2();
        void ReadInAcm3();
        void ReadInXML();

        void WriteInFind(vertex*);
        void WriteInPython(vertex*, int level = -1);
        void WriteInAcm1();
        void WriteInAcm2();
        void WriteInAcm3();
        void WriteInXML(vertex*, int level = -1);

        void AddChildInFind(vertex* parent, string path, unsigned long & id);
};

void Dir::WriteInXML(vertex* parent, int level)
{
    for (int i = 0; i < level; i++)
    {
        cout << "  ";
    }

    if (parent != root)
    {
        if (parent->childs.size() == 0)
        {
            cout << "<file name='" << parent->GetName() << "' id='" << parent->GetId() << "'/>" << endl;
        }
        else
        {
            cout << "<dir name='" << parent->GetName() << "' id='" << parent->GetId() << "'>" << endl;
        }
    }

    for (map <unsigned long, vertex*>::iterator i = parent->childs.begin(); i != parent->childs.end(); i++)
    {
      WriteInXML(i->second, level+1);
    }

    if (parent->childs.size() && parent->GetName() != "")
    {
        for (int i = 0; i < level; i++)
        {
            cout << "  ";
        }
        cout << "</dir>" << endl;
    }
}

pair <string, string> GetNameAndId(string line)
{
    string name = "", id = "";
    int count = 0;
    for (int i = 0; i < line.length(); i++)
    {
        if ((line[i] == '\''))
        {
            count++;
        }
        else
        {
            if (count == 1)
            {
                name += line[i];
            }
            if (count == 3)
            {
                id += line[i];
            }
        }
    }
    return pair<string,string>(name,id);
}

void Dir::ReadInXML()
{
    string line = "";

    string name;
    unsigned long id;

    if (root != NULL)
    {
        delete root;
    }

    root = new vertex("", (unsigned long)(-1));

    vertex* parent = root;

    while (true)
    {
      char c;
        for(c = getchar(); c == ' '; c = getchar());
        if (c == EOF)
        {
         SetSize(vertexes.size());
            return;
        }
        ungetc(c, stdin);

        getline(cin, line);

        if (string(line, 0, 5) == "<file")
        {
         pair <string, string> tmp = GetNameAndId(line);

            vertex* child = new vertex(tmp.first, StrToUnsignedLong(tmp.second), parent);

            AddChild(parent, child);
        }
        else
        {
            if (string(line, 0, 6) == "</dir>")
            {
                parent = parent->GetParent();
            }
            else
            {
             pair <string, string> tmp = GetNameAndId(line);

                vertex* child = new vertex(tmp.first, StrToUnsignedLong(tmp.second), parent);

                AddChild(parent, child);

                parent = child;
            }
        }

        if (parent == root)
        {
            //return;
        }
    }

}

void Dir::WriteInAcm3()
{
    cout << GetSize() << endl;

    for (map < unsigned long, vertex* >::iterator i = vertexes.begin(); i != vertexes.end(); i++)
    {
        cout << i->second->GetName() << " " << i->first << endl;
    }

    for (map < unsigned long, vertex* >::iterator i = vertexes.begin(); i != vertexes.end(); i++)
    {
        vertex* parent = i->second;
        for (map < unsigned long, vertex* >::iterator j = parent->childs.begin(); j != parent->childs.end(); j++)
        {
            cout << i->first << ' ' << j->first << endl;
        }
    }
}

void Dir::ReadInAcm3()
{
    int n;
    cin >> n;

    SetSize(n);

    string name;
    unsigned long id;

    if (root != NULL)
    {
        delete root;
    }

    root = new vertex("", (unsigned long)(-1));

    for (int i = 0; i < n; i++)
    {
        cin >> name >> id;
        AddVertex(new vertex(name, id));
        if (id == 0)
        {
            GetVertexById(id)->SetParent(root);
            root->AddChild(GetVertexById(id));
        }
    }

    for (int i = 1; i < n; i++)
    {
        int k, p;
        cin >> k >> p;

        vertex* child = GetVertexById(p);

      child->SetParent( GetVertexById(k) );
        GetVertexById(k)->AddChild(child);
    }
}

void Dir::ReadInAcm2()
{
    int n;
    cin >> n;

    SetSize(n);

    string name;
    unsigned long id;

    if (root != NULL)
    {
        delete root;
    }

    root = new vertex("", (unsigned long)(-1));

    for (int i = 0; i < n; i++)
    {
        cin >> name >> id;
        AddVertex(new vertex(name, id));
    }

    for (map < unsigned long, vertex* >::iterator i = vertexes.begin(); i != vertexes.end(); i++)
    {
        long long p;
        cin >> p;

        vertex* child = i->second;

        if (p == -1)
        {
           child->SetParent(root);
            root->AddChild(child);
        }
        else
        {
            unsigned long k = (unsigned long)p;
            child->SetParent( GetVertexById(p) );
            GetVertexById(p)->AddChild(child);
        }
    }
}

void Dir::WriteInAcm2()
{
    cout << GetSize() << endl;

    for (map < unsigned long, vertex* >::iterator i = vertexes.begin(); i != vertexes.end(); i++)
    {
        cout << i->second->GetName() << ' ' << i->first << endl;
    }

    for (map < unsigned long, vertex* >::iterator i = vertexes.begin(); i != vertexes.end(); i++)
    {
        vertex* child = i->second;
        if (child->GetParent() == root)
        {
            cout << -1 << endl;
        }
        else
        {
            cout << child->GetParent()->GetId() << endl;
        }
    }
}

void Dir::ReadInAcm1()
{
    int n;
    cin >> n;

    SetSize(n);

    string name;
    unsigned long id;

    if (root != NULL)
    {
        delete root;
    }

    root = new vertex("", (unsigned long)(-1));

    for (int i = 0; i < n; i++)
    {
        cin >> name >> id;
        AddVertex(new vertex(name, id));
        if (id == 0)
        {
            GetVertexById(id)->SetParent(root);
            root->AddChild(GetVertexById(id));
        }
    }


    for (map < unsigned long, vertex* >::iterator i = vertexes.begin(); i != vertexes.end(); i++)
    {
        vertex* parent = i->second;

        int k;
          cin >> k;

        for (int j = 0; j < k; j++)
        {
            unsigned long p;
            cin >> p;
            parent->AddChild(GetVertexById(p));
        }
    }
}

void Dir::WriteInAcm1()
{
    cout << GetSize() << endl;

    for (map < unsigned long, vertex* >::iterator i = vertexes.begin(); i != vertexes.end(); i++)
    {
        cout << i->second->GetName() << " " << i->first << endl;
    }

    for (map < unsigned long, vertex* >::iterator i = vertexes.begin(); i != vertexes.end(); i++)
    {
        vertex* parent = i->second;
        cout << parent->childs.size();
        for (map < unsigned long, vertex* >::iterator j = parent->childs.begin(); j != parent->childs.end(); j++)
        {
            cout << ' ' << j->first;
        }
        cout << endl;
    }
}

void Dir::ReadInPython()
{
    int n;
    cin >> n;

    SetSize(n);

    char c;
    int spacesCount = 0;

    if (root != NULL)
    {
        delete root;
    }

    root = new vertex("", (unsigned long)(-1));

    vertex* currentParent = NULL;
    int currentLevel = -1;

    string name;
    unsigned long id;

   vertex* last_child = root;

    for (int i = 0; i < n; i++)
    {
        for (getchar(), spacesCount = 0; c = getchar(), c == ' '; spacesCount++);
        ungetc(c, stdin);

        cin >> name >> id;

        int level = spacesCount/4;

          vertex* new_child = new vertex(name, id);

        if (level > currentLevel)
        {
            currentParent = last_child;
        }

        if (level < currentLevel)
        {
            for (int j = 0; j < currentLevel-level; j++)
            {
                currentParent = currentParent->GetParent();
            }
        }

        AddChild(currentParent, new_child);

        last_child = new_child;
        currentLevel = level;
    }
}

void Dir::WriteInPython(vertex* parent, int level)
{
    if (parent == root)
    {
        cout << GetSize() << endl;
    }
    for (int i = 0; i < level; i++)
    {
        cout << "    ";
    }

    if (parent != root)
    {
        cout << parent->GetName() << ' ' << parent->GetId() << endl;
    }

    for (map <unsigned long, vertex*>::iterator i = parent->childs.begin(); i != parent->childs.end(); i++)
    {
      WriteInPython(i->second, level+1);
    }
}

void Dir::WriteInFind(vertex* parent)
{
    cout << GetSize() << endl;
    for (map < unsigned long, vertex* >::iterator i = vertexes.begin(); i != vertexes.end(); i++)
    {
        vertex* tmp = i->second;
        string out;
        while (tmp != NULL)
        {
            if (out == "" || tmp == root)
            {
                out = out + tmp->GetName();
            }
            else
            {
                out = tmp->GetName() + "/" + out;
            }

            tmp = tmp->GetParent();
        }

        cout << out << " " << i->second->GetId() << endl;
    }
}

void Dir::ReadInFind()
{
    int n;
    cin >> n;

    SetSize(n);

    string path;
    unsigned long id;

    if (root != NULL)
    {
        delete root;
    }

    root = new vertex("", (unsigned long)(-1));

    for (int i = 0; i < n; i++)
    {
        cin >> path >> id;

      AddChildInFind(root, path, id);
    }
}

void Dir::AddChildInFind(vertex* parent, string path, unsigned long & id)
{
    size_t pos = path.find('/');
    if (pos == string::npos)
    {
      AddChild(parent, new vertex(path, id, parent));
      return;
    }

    string new_path(path, pos+1, path.length()-pos-1);
    string child_name(path, 0, pos);

    AddChildInFind(parent->NextChild(child_name), new_path, id);
}

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    Dir a;
    string in_format;
    string out_format;

    cin >> in_format;
    cin >> out_format;
    getchar();

    a.Read(in_format);
    a.Write(out_format);
}

Автор: на

4 комментария:

  1. Unknown12 июня 2012 г. в 23:31

    Переписываешься с уткой:)
    А ещё тебе лень писать самому то, что ты решил отскиринить :Р
    Цём тебя. Устал ты просто.

    ОтветитьУдалить
  2. Unknown12 июня 2012 г. в 23:32

    Ахах, флиртомания +64. Ууууу, спалилсо

    ОтветитьУдалить
  3. Unknown12 июня 2012 г. в 23:34

    XDD Это мне валентинку кто-то послал на дсв пол года назад, а для её просмотря сказали, что поставить надо :)

    ОтветитьУдалить

Подписаться на: Комментарии к сообщению (Atom)