Submission #1258064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258064		stapanulocu1	Souvenirs (IOI25_souvenirs)	C++20	39 / 100	1079 ms	908 KiB

souvenirs

#include <bits/stdc++.h>
using namespace std;

const int N = 100;

long long ell[100] = {2660822841688, 1543875428686, 854806807668, 458519997429, 239172625298,
                      131829070422, 67618394369, 36652285201, 20851110356, 11296028942,
                      5745612859, 3007239918, 1815432867, 1111304349, 699498544, 388399115,
                      222002146, 142384930, 73211028, 40503786, 26228775, 13711027, 8154615,
                      4090858, 2686055, 1350405, 677104, 361883, 182963, 111440, 58780, 31043,
                      16035, 9703, 5634, 3002, 1624, 1040, 567, 367, 189, 112, 72, 39, 21,
                      11, 6, 4, 2, 1};

int n;

pair<vector<int>, long long> transaction(long long M);
/*
pair<vector<int>, long long> transaction(long long M)
{
    vector<int> a;

    for (int i = 0; i < n; ++i)
    {
        if (ell[i] <= M)
        {
            M -= ell[i];
            a.push_back(i);
        }
    }

    return pair<vector<int>, long long>(a, M);
}*/

struct el
{
    vector<int> s;
    long long b, r;
    bool queried = 0;
};

vector<el> q;
long long value[N];
int number[N];

void update_data(el &r);

void check_to_remove(el r)
{
    if (r.s.size() == 1)
    {
        value[r.s[0]] = r.b - r.r;
        for (int i = 0; i < (int)q.size(); ++i)
            update_data(q[i]);
    }
}

void figure_smallest(el &va);

void update_data(el &r)
{
    bool updated = false;
    for (int i = 0; i < (int)r.s.size(); ++i)
    {
        if (value[r.s[i]])
        {
            r.b -= value[r.s[i]];

            r.s.erase(r.s.begin() + i);
            updated = true;
            r.queried = 0;

            --i;
        }
    }

    check_to_remove(r);

    // if (r.s.size() > 1 && updated)
    //{
    //     figure_smallest(r);
    // }
}

void do_q(long long a)
{
    pair<vector<int>, long long> result = transaction(a);
    el b;
    b.s = result.first;
    b.b = a;
    b.r = result.second;

    for (int i = 0; i < (int)b.s.size(); ++i)
    {
        number[b.s[i]]++;
    }

    update_data(b);

    q.push_back(b);
}

void recheckAvg(long long &avg, long long num, el va)
{
    bool any_good = false;
    for (int i = va.s[0]; i < va.s[va.s.size() - 1] - 1; ++i)
    {
        if (value[i] != 0)
            any_good = true;
        if (value[i] != 0 && value[i + 1] == 0 && number[i + 1] < i + 1)
        {
            avg = value[i] - 1;
            return;
        }
    }
    if (any_good)
        avg = 0;
}

void figure_smallest(el &va)
{

    if (va.s.size() == 1)
    {
        check_to_remove(va);
        return;
    }
    if (va.s.size() == 0)
        return;
    if (va.queried)
        return;
    va.queried = 1;

    long long avg = (va.b - va.r) / (long long)va.s.size();

    recheckAvg(avg, (long long)va.s.size(), va);
    if (avg == 0)
        return;
    do_q(avg);
    figure_smallest(q.back());
}

void finish_all()
{
    for (int i = 0; i < n; ++i)
    {
        if (value[i] == 0)
        {
            while (1)
                ;
        }
        while (number[i] < i)
        {
            do_q(value[i]);
        }
    }
}

bool don()
{
    for (int i = 0; i < n; ++i)
        if (!value[i])
            return false;
    return true;
}

void buy_souvenirs(int nu, long long P0)
{
    n = nu;
    value[0] = P0;

    while (!don())
    {
        for (int j = n - 2; j >= 0; --j)
        {
            if (number[j + 1] < j + 1 && value[j] != 0 && value[j + 1] == 0)
            {
                do_q(value[j] - 1);
                break;
            }
        }

        for (int i = q.size() - 1; i >= 0; --i)
        {
            check_to_remove(q[i]);
        }
        for (int i = q.size() - 1; i >= 0; --i)
        {
            if (q[i].s.size() == 0)
            {
                q.erase(q.begin() + i);
                --i;
            }
            if (q[i].s.size() != 0 && !q[i].queried)
            {
                figure_smallest(q[i]);
            }
        }
    }
    /*
        for (int j = 1; j < n; ++j)
        {
            if (value[j] == 0)
                do_q(value[j - 1] - 1);

            while (value[j] == 0)
            {
                for (int i = 0; i < (int)q.size(); ++i)
                {
                    check_to_remove(q[i]);

                    if (q[i].s.size() != 0)
                    {
                        figure_smallest(q[i]);
                    }
                }
            }
            q.clear();
        }*/

    finish_all();
}
/*
int main()
{
    buy_souvenirs(50, 2660822841688);

    cerr << "Result";
    for (int i = 0; i < n; ++i)
        cerr << number[i] << " ";
    return 0;
}*/

• Subtask 0: 0 / 0
• Subtask 1: 4 / 4
• Subtask 2: 3 / 3
• Subtask 3: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 0 / 28
• Subtask 6: 0 / 33