Submission #1031961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031961		abczz	Longest Trip (IOI23_longesttrip)	C++17	15 / 100	3067 ms	348 KiB

longesttrip

#include "longesttrip.h"
#include <iostream>
#include <vector>
#include <random>
#include <queue>
#include <algorithm>
#define ll int

using namespace std;

std::vector<int> longest_trip(int N, int D)
{
    random_device rd;
    mt19937_64 mt(rd());
    vector <int> V, U, F, X[257], perm;
    bool res;
    bool B[257];
    ll x, y;
    for (int i=0; i<N; ++i) {
        X[i].clear();
        B[i] = 0;
        perm.push_back(i);
    }
    if (D == 3) {
        for (int i=0; i<N; ++i) V.push_back(i);
        return V;
    }
    else if (D == 2) {
        for (int i=1; i<N; ++i) {
            res = are_connected({0}, {i});
            if (res) {
                B[0] = B[i] = 1;
                U.push_back(0);
                V.push_back(i);
                break;
            }
        }
        for (int i=1; i<N; ++i) {
            if (B[i]) continue;
            res = are_connected({U.back()}, {i});
            if (res) U.push_back(i);
            else V.push_back(i);
        }
        for (int i=U.size()-1; i>=0; --i) F.push_back(U[i]);
        for (auto u : V) F.push_back(u);
        return F;
    }
    else {
        F.push_back(perm[0]);
        for (int i=1; i<N; ++i) {
            U.push_back(perm[i]);
            X[perm[i]].push_back(perm[i]);
        }
        while (F.size() < N) {
            V.clear();
            while (!U.empty()) {
                auto u = U.back();
                U.pop_back();
                res = are_connected({F.back()}, {X[u].back()});
                if (res) {
                    while (!X[u].empty()) {
                        auto v = X[u].back();
                        X[u].pop_back();
                        F.push_back(v);
                    }
                    break;
                }
                else {
                    V.push_back(u);
                }
            }
            if (res) {
                if (V.size() > 1) swap(V[0], V[1]);
                for (int i=1; i<V.size(); ++i) {
                    X[V[0]].push_back(V[i]);
                }
                if (!V.empty()) {
                    if (!U.empty()) {
                        auto v = U.back();
                        U.pop_back();
                        U.push_back(V[0]);
                        U.push_back(v);
                    }
                    else U.push_back(V[0]);
                }
            }
            else break;
        }
        if (F.size() == N) return F;
        if (V.size() > 1) swap(V[0], V[1]);
        for (int i=1; i<V.size(); ++i) {
            X[V[0]].push_back(V[i]);
        }
        if (X[V[0]].size() > 1) {
            res = are_connected({F.back()}, {X[V[0]][0]});
            if (res) {
                for (auto v : X[V[0]]) F.push_back(v);
                return F;
            }
        }
        if (F.size() > 1) {
            res = are_connected({F[0]}, {X[V[0]].back()});
            if (res) {
                reverse(F.begin(), F.end());
                while (!X[V[0]].empty()) {
                    auto v = X[V[0]].back();
                    X[V[0]].pop_back();
                    F.push_back(v);
                }
                return F;
            }
            res = are_connected({F[0]}, {X[V[0]][0]});
            if (res) {
                reverse(F.begin(), F.end());
                for (auto v : X[V[0]]) F.push_back(v);
                return F;
            }
        }
        res = are_connected(F, X[V[0]]);
        if (!res) {
            if (F.size() > X[V[0]].size()) return F;
            else return X[V[0]];
        }
        ll l = 0, r = X[V[0]].size()-1, mid;
        vector <ll> tmp;
        while (l < r) {
            tmp.clear();
            mid = (l+r)/2;
            for (int i=l; i<=mid; ++i) tmp.push_back(X[V[0]][i]);
            res = are_connected(F, tmp);
            if (res) r = mid;
            else l = mid + 1;
        }
        y = l;
        l = 0, r = F.size()-1;
        while (l < r) {
            tmp.clear();
            mid = (l+r)/2;
            for (int i=l; i<=mid; ++i) tmp.push_back(F[i]);
            res = are_connected(tmp, {X[V[0]][y]});
            if (res) r = mid;
            else l = mid + 1;
        }
        x = l;
        U.clear();
        for (int i=x+1; i<F.size(); ++i) U.push_back(F[i]);
        for (int i=0; i<=x; ++i) U.push_back(F[i]);
        for (int i=y; i<X[V[0]].size(); ++i) U.push_back(X[V[0]][i]);
        for (int i=0; i<y; ++i) U.push_back(X[V[0]][i]);
        return U;
    }
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:54:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |         while (F.size() < N) {
      |                ~~~~~~~~~^~~
longesttrip.cpp:74:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |                 for (int i=1; i<V.size(); ++i) {
      |                               ~^~~~~~~~~
longesttrip.cpp:89:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |         if (F.size() == N) return F;
      |             ~~~~~~~~~^~~~
longesttrip.cpp:91:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for (int i=1; i<V.size(); ++i) {
      |                       ~^~~~~~~~~
longesttrip.cpp:146:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |         for (int i=x+1; i<F.size(); ++i) U.push_back(F[i]);
      |                         ~^~~~~~~~~
longesttrip.cpp:148:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |         for (int i=y; i<X[V[0]].size(); ++i) U.push_back(X[V[0]][i]);
      |                       ~^~~~~~~~~~~~~~~

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