oj.uz

Submission #839747

# Submission time Handle Problem Language Result Execution time Memory
839747 2023-08-30T15:49:51 Z model_code Longest Trip (IOI23_longesttrip) C++17
15 / 100
 1000 ms 444 KB 
// partially_correct/solution-allEdges.cpp

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

bool conn[256][256];

bool connected(const std::vector<int> &a, const std::vector<int> &b)
{
    for (int i : a)
    {
        for (int j : b)
        {
            if (conn[i][j])
                return true;
        }
    }
    return false;
}

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

void combine(std::deque<int> &line1, std::deque<int> &line2)
{
    if (line2.empty())
        return;

    if (connected({line1.back()}, {line2.back()}))
    {
        while (!line2.empty())
        {
            line1.push_back(line2.back());
            line2.pop_back();
        }
        return;
    }
    if (connected({line1.back()}, {line2.front()}))
    {
        while (!line2.empty())
        {
            line1.push_back(line2.front());
            line2.pop_front();
        }
        return;
    }
    if (connected({line1.front()}, {line2.back()}))
    {
        while (!line2.empty())
        {
            line1.push_front(line2.back());
            line2.pop_back();
        }
        return;
    }
    if (connected({line1.front()}, {line2.front()}))
    {
        while (!line2.empty())
        {
            line1.push_front(line2.front());
            line2.pop_front();
        }
        return;
    }

    std::vector<int> l1;
    l1.clear();
    std::vector<int> l2;
    l2.clear();

    for (int i : line1)
        l1.push_back(i);
    for (int i : line2)
        l2.push_back(i);

    if (!connected(l1, l2))
        return;

    int a = 0, b = line2.size() - 1;
    while (a != b)
    {
        std::vector<int> vec(line2.begin() + a, line2.begin() + (a + b) / 2 + 1);
        if (connected(l1, vec))
        {
            b = (a + b) / 2;
        }
        else
        {
            a = (a + b) / 2 + 1;
        }
    }
    int pos = a;

    a = 0;
    b = line1.size() - 1;
    while (a != b)
    {
        std::vector<int> vec(line1.begin() + a, line1.begin() + (a + b) / 2 + 1);
        if (connected(vec, {l2[pos]}))
        {
            b = (a + b) / 2;
        }
        else
        {
            a = (a + b) / 2 + 1;
        }
    }
    int pos2 = a;

    if (pos2 != (int)line1.size() - 1)
        std::rotate(line1.begin(), line1.begin() + pos2 + 1, line1.end());
    if (pos != (int)line2.size() - 1)
        std::rotate(line2.begin(), line2.begin() + pos + 1, line2.end());

    while (!line2.empty())
    {
        line1.push_back(line2.back());
        line2.pop_back();
    }
}

std::vector<int> longest_trip(int N, int /*D*/)
{
    for (int i = 1; i < N; i++)
    {
        for (int j = 0; j < i; j++)
        {
            conn[i][j] = are_connected({i}, {j});
            conn[j][i] = conn[i][j];
        }
    }

    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 (connected({line1.back()}, {ids[i]}))
        {
            line1.push_back(ids[i]);
            separated = false;
        }
        else if (separated)
        {
            line2.push_back(ids[i]);
        }
        else if (connected({line2.back()}, {ids[i]}))
        {
            line2.push_back(ids[i]);
            separated = true;
        }
        else
        {
            if (i < N - 2)
            {
                bool c1 = connected({ids[i]}, {ids[i + 1]});
                bool c2 = 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> l1;
    l1.clear();
    std::vector<int> l2;
    l2.clear();

    for (int i : line1)
        l1.push_back(i);
    for (int i : line2)
        l2.push_back(i);

    combine(line1, line2);

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

    /*while(cc < N * (N-1) / 2){
        connected({0}, {1});
    }*/

    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 318 ms 344 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 252 KB Output is correct
2 Correct 36 ms 208 KB Output is correct
3 Correct 211 ms 300 KB Output is correct
4 Correct 402 ms 336 KB Output is correct
5 Correct 956 ms 328 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 208 KB Output is correct
2 Correct 23 ms 208 KB Output is correct
3 Correct 153 ms 300 KB Output is correct
4 Correct 426 ms 300 KB Output is correct
5 Correct 894 ms 336 KB Output is correct
6 Correct 15 ms 252 KB Output is correct
7 Correct 27 ms 208 KB Output is correct
8 Correct 220 ms 296 KB Output is correct
9 Correct 313 ms 208 KB Output is correct
10 Correct 845 ms 444 KB Output is correct
11 Correct 796 ms 312 KB Output is correct
12 Correct 875 ms 420 KB Output is correct
13 Correct 828 ms 336 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 208 KB Output is correct
2 Correct 27 ms 208 KB Output is correct
3 Correct 146 ms 300 KB Output is correct
4 Correct 526 ms 296 KB Output is correct
5 Correct 742 ms 316 KB Output is correct
6 Correct 11 ms 208 KB Output is correct
7 Correct 33 ms 280 KB Output is correct
8 Correct 215 ms 288 KB Output is correct
9 Correct 337 ms 304 KB Output is correct
10 Correct 773 ms 316 KB Output is correct
11 Correct 903 ms 332 KB Output is correct
12 Correct 976 ms 332 KB Output is correct
13 Execution timed out 1143 ms 444 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 208 KB Output is correct
2 Correct 35 ms 208 KB Output is correct
3 Partially correct 146 ms 300 KB Output is partially correct
4 Partially correct 489 ms 288 KB Output is partially correct
5 Execution timed out 1146 ms 332 KB Time limit exceeded
6 Halted 0 ms 0 KB -