Submission #1250746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250746		MKopchev	Souvenirs (IOI25_souvenirs)	C++20	25 / 100	12 ms	412 KiB

souvenirs

#include "souvenirs.h"
#include <utility>
#include <vector>
#include <iostream>

const int nmax=1e2+42;

long long known[nmax];
int seen[nmax];

std::vector< std::pair< std::vector<int>, long long> > known_sums;

void add_line(long long M)
{
    std::pair< std::vector<int>, long long> outp=transaction(M);

    outp.second=M-outp.second;

    for(auto pos:outp.first)
        seen[pos]++;

    known_sums.push_back(outp);

    bool change=1;

    while(change)
    {
        change=0;

        std::vector< std::pair< std::vector<int>, long long> > new_known_sums={};

        for(auto line:known_sums)
        {
            long long new_sum=line.second;
            std::vector<int> new_positions={};

            for(auto pos:line.first)
                if(known[pos])new_sum-=known[pos];
                else new_positions.push_back(pos);

            if(new_positions.size()!=line.first.size())change=1;

            if(new_positions.size()==0)continue;
            if(new_positions.size()==1)
            {
                known[new_positions[0]]=new_sum;
            }
            else
            {
                new_known_sums.push_back({new_positions,new_sum});
            }
        }

        known_sums=new_known_sums;
    }
}

int get_last_non_suffix(int N)
{
    int pos=N-1;

    while(known[pos])pos--;

    while(known[pos]==0)pos--;

    return pos;
}

void buy_souvenirs(int N, long long P0)
{
    known[0]=P0;

    for(int i=1;i<N;i++)
    {
        int pos=get_last_non_suffix(N);

        if(known_sums.size()==0||known_sums.back().first[0]<pos)
        {
            add_line(known[pos]-1);
        }
        else
        {
            add_line(known_sums.back().second/known_sums.back().first.size());
        }
    }

    for(int i=0;i<N;i++)
        while(seen[i]<i)
        {
            add_line(known[i]);
        }
}

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