Submission #876834

#	Time	Username	Problem	Language	Result	Execution time	Memory
876834		MinaRagy06	Longest Trip (IOI23_longesttrip)	C++17	85 / 100	20 ms	884 KiB

longesttrip

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

vector<int> longest_trip(int n, int d) {
    if (d == 3) {
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            ans.push_back(i);
        }
        return ans;
    } else if (d == 2) {
        vector<int> rem;
        for (int i = 1; i < n; i++) {
            rem.push_back(i);
        }
        vector<int> ans;
        ans.push_back(0);
        while (rem.size()) {
            if (are_connected({ans.back()}, {rem.back()})) {
                ans.push_back(rem.back());
                rem.pop_back();
            } else {
                int x = rem.back();
                rem.pop_back();
                if (rem.size()) {
                    ans.push_back(rem.back());
                    rem.pop_back();
                    rem.push_back(x);
                } else {
                    rem.push_back(x);
                    break;
                }
            }
        }
        if (rem.size()) {
            reverse(ans.begin(), ans.end());
            ans.push_back(rem.back());
        }
        return ans;
    } else {
        vector<int> v[2];
        v[0].push_back(0);
        for (int i = 1; i < n; i++) {
            if (are_connected({v[0].back()}, {i})) {
                v[0].push_back(i);
            } else if (v[1].size() && are_connected({v[1].back()}, {i})) {
                v[1].push_back(i);
            } else {
                reverse(v[1].begin(), v[1].end());
                for (auto j : v[1]) {
                    v[0].push_back(j);
                }
                v[1] = {i};
            }
        }
        if (v[1].empty()) return v[0];
        if (are_connected({v[1][0]}, {v[0][0]})) {
            reverse(v[0].begin(), v[0].end());
            for (auto i : v[1]) {
                v[0].push_back(i);
            }
            return v[0];
        } else if (are_connected({v[1][0]}, {v[0].back()})) {
            for (auto i : v[1]) {
                v[0].push_back(i);
            }
            return v[0];
        } else if (are_connected({v[1].back()}, {v[0][0]})) {
            for (auto i : v[0]) {
                v[1].push_back(i);
            }
            return v[1];
        } else if (are_connected({v[1].back()}, {v[0].back()})) {
            reverse(v[1].begin(), v[1].end());
            for (auto i : v[1]) {
                v[0].push_back(i);
            }
            return v[0];
        } else {
            int l = 0, r = v[0].size() - 1;
            while (l <= r) {
                int md = (l + r) >> 1;
                vector<int> cur;
                for (int k = l; k <= md; k++) {
                    cur.push_back(v[0][k]);
                }
                if (are_connected(cur, v[1])) {
                    r = md - 1;
                } else {
                    l = md + 1;
                }
            }
            int i = l;
            if (i == v[0].size()) {
                if (v[0].size() > v[1].size()) {
                    return v[0];
                } else {
                    return v[1];
                }
            }
            l = 0, r = v[1].size();
            while (l <= r) {
                int md = (l + r) >> 1;
                vector<int> cur;
                for (int k = l; k <= md; k++) {
                    cur.push_back(v[1][k]);
                }
                if (are_connected({v[0][i]}, cur)) {
                    r = md - 1;
                } else {
                    l = md + 1;
                }
            }
            int j = l;
            vector<int> x[2];
            for (int k = i + 1; k < v[0].size(); k++) {
                x[0].push_back(v[0][k]);
            }
            for (int k = 0; k <= i; k++) {
                x[0].push_back(v[0][k]);
            }
            for (int k = j + 1; k < v[1].size(); k++) {
                x[1].push_back(v[1][k]);
            }
            for (int k = 0; k <= j; k++) {
                x[1].push_back(v[1][k]);
            }
            reverse(x[1].begin(), x[1].end());
            vector<int> ans = x[0];
            for (auto k : x[1]) {
                ans.push_back(k);
            }
            return ans;
            /*for (int i = 0; i < v[0].size(); i++) {
                for (int j = 0; j < v[1].size(); j++) {
                    if (are_connected({v[0][i]}, {v[1][j]})) {
                        vector<int> x[2];
                        for (int k = i + 1; k < v[0].size(); k++) {
                            x[0].push_back(v[0][k]);
                        }
                        for (int k = 0; k <= i; k++) {
                            x[0].push_back(v[0][k]);
                        }
                        for (int k = j + 1; k < v[1].size(); k++) {
                            x[1].push_back(v[1][k]);
                        }
                        for (int k = 0; k <= j; k++) {
                            x[1].push_back(v[1][k]);
                        }
                        reverse(x[1].begin(), x[1].end());
                        vector<int> ans = x[0];
                        for (auto k : x[1]) {
                            ans.push_back(k);
                        }
                        return ans;
                    }
                }
            }
            if (v[0].size() > v[1].size()) {
                return v[0];
            } else {
                return v[1];
            }*/
        }
    }
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:95:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             if (i == v[0].size()) {
      |                 ~~^~~~~~~~~~~~~~
longesttrip.cpp:117:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |             for (int k = i + 1; k < v[0].size(); k++) {
      |                                 ~~^~~~~~~~~~~~~
longesttrip.cpp:123:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |             for (int k = j + 1; k < v[1].size(); k++) {
      |                                 ~~^~~~~~~~~~~~~

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