Menu

Informatics Задача №112695. Файловое дерево

February 17, 2017 - informatics.mccme.ru

Language: C++

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>

using namespace std;

vector <vector <int> > folderGraph;

int freeFolder = 0;

vector <int> p;
vector <int> notFilesCnt;
int Folders = 0;
void fillGraph(int v, int k, int p)
{
    ::p[v] = p;
    if (k <= 0)
    {
        return;
    }
    ++Folders;
    folderGraph[v].resize(k);
    for (int i = 0; i < k; ++i)
    {
        folderGraph[v][i] = ++freeFolder;
        if (k - i - 2 > 0)
            ++notFilesCnt[v];
        fillGraph(freeFolder, k - i - 2, v);
    }
}

int n;
int curN;

struct Comp
{
    bool operator()(int i, int j)
    {
        return folderGraph[i].size() < folderGraph[j].size();
    }
};

multiset <int, Comp> onlyFilesFolders;

void deleteFolders()
{
    onlyFilesFolders.clear();
    for (size_t i = 0; i < folderGraph.size(); ++i)
    {
        if (folderGraph[i].size() && !notFilesCnt[i])
            onlyFilesFolders.insert(i);
    }
    while (onlyFilesFolders.size() && curN >= n)
    {
        int i = *onlyFilesFolders.begin();
        onlyFilesFolders.erase(onlyFilesFolders.begin());
        int deleted = folderGraph[i].size();
        --deleted;
        if (curN - deleted >= n)
        {
            curN -= deleted;
            folderGraph[i].clear();
            --Folders;
            --notFilesCnt[p[i]];
            if (notFilesCnt[p[i]] == 0)
                onlyFilesFolders.insert(p[i]);
        }
        else
        {
            break;
        }
    }
}


int main()
{
    scanf("%d", &n);
    if (n == 1)
    {
        printf("1 0\n");
        printf("1 FILE_1\n");
        return 0;
    }
    int k = 1;
    vector <int> f(2);
    f[0] = 1;
    f[1] = 1;
    for (int i = 2; i < n + 10; ++i)
    {
        f.push_back(0);
        f[i] = f[i - 1] + f[i - 2];
        if (f[i] >= n)
        {
            k = i;
            break;
        }
    }
    f.push_back(0);
    f[k + 1] = f[k] + f[k - 1];
    //for (k = 1; (1 << (k - 1)) < n; ++k);
    folderGraph.resize(f[k + 1]);
    p.resize(f[k + 1]);
    notFilesCnt.assign(f[k + 1], 0);
    curN = f[k];
    //leaf is a file;
    fillGraph(freeFolder, k, 0);
    deleteFolders();
    printf("%d %d\n", k, Folders - 1);
    int freeFolderIndex = 0;
    int freeFileIndex = 0;
    queue<pair<int, int> > q; //(old, new);
    q.push(make_pair(0, freeFolderIndex));
    while (q.size())
    {
        pair<int, int> v = q.front();
        q.pop();
        vector <pair<int, int> > output;
        for (size_t i = 0; i < folderGraph[v.first].size(); ++i)
        {
            if (folderGraph[folderGraph[v.first][i]].size())
            {
                q.push(make_pair(folderGraph[v.first][i], ++freeFolderIndex));
                output.push_back(make_pair(0, freeFolderIndex));
            }
            else
            {
                if (freeFileIndex + 1 <= n)
                    output.push_back(make_pair(1, ++freeFileIndex));
            }
        }
        printf("%d ", output.size());
        for (size_t i = 0; i < output.size(); ++i)
        {
            if (output[i].first)
                printf("FILE_");
            else
                printf("FOLDER_");
            printf("%d ", output[i].second);
        }
        printf("\n");
    }
    return 0;
}

(22)

It's only fair to share...Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInShare on VK

Author of this post : UnknownA AuthorA

Leave a Reply

Your email address will not be published. Required fields are marked *