Submission #839727

#	Time	Username	Problem	Language	Result	Execution time	Memory
839727		model_code	Longest Trip (IOI23_longesttrip)	C++17	25 / 100	12 ms	288 KiB

longesttrip

// correct/solution-subtask3.cpp

#include "longesttrip.h"
#include <algorithm>
#include <random>
#include <deque>

void conc(std::deque<int> &l1, std::deque<int> &l2)
{
    while (!l2.empty())
    {
        l1.push_back(l2.back());
        l2.pop_back();
    }
}

std::vector<int> longest_trip(int N, int /*D*/)
{
    srand(time(0));
    std::vector<int> ids(N);
    for (int i = 0; i < N; i++)
        ids[i] = i;
    random_shuffle(ids.begin(), ids.end());

    std::deque<int> line1;
    line1.clear();
    std::deque<int> line2;
    line2.clear();

    line1.push_back(ids[0]);
    line2.push_back(ids[1]);

    bool separated = false;

    for (int i = 2; i < N; i++)
    {
        if (are_connected({line1.back()}, {ids[i]}))
        {
            line1.push_back(ids[i]);
            separated = false;
        }
        else if (separated)
        {
            line2.push_back(ids[i]);
        }
        else if (are_connected({line2.back()}, {ids[i]}))
        {
            line2.push_back(ids[i]);
            separated = true;
        }
        else
        {
            if (i < N - 2)
            {
                bool c1 = are_connected({ids[i]}, {ids[i + 1]});
                bool c2 = are_connected({ids[i]}, {ids[i + 2]});
                if (c1 && c2)
                {
                    conc(line1, line2);
                    line2.push_back(ids[i + 1]);
                    line2.push_back(ids[i]);
                    line2.push_back(ids[i + 2]);
                }
                else if (!c1 && !c2)
                {
                    line1.push_back(ids[i + 1]);
                    line1.push_back(ids[i + 2]);
                    conc(line1, line2);
                    line2.push_back(ids[i]);
                }
                else
                {
                    if (!c1)
                        line1.push_back(ids[i + 1]);
                    else
                        line1.push_back(ids[i + 2]);
                    conc(line1, line2);
                    if (!c1)
                        line2.push_back(ids[i + 2]);
                    else
                        line2.push_back(ids[i + 1]);
                    line2.push_back(ids[i]);
                }
                i += 2;
            }
            else
            {
                conc(line1, line2);
                line2.push_back(ids[i]);
            }
            separated = false;
        }
    }

    if (line1.size() < line2.size())
        swap(line1, line2);

    std::vector<int> ans;
    ans.clear();
    for (int i : line1)
        ans.push_back(i);
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 25 / 25
• Subtask 4: 0 / 60