Submission #845799

#	Time	Username	Problem	Language	Result	Execution time	Memory
845799		vjudge1	Longest Trip (IOI23_longesttrip)	C++17	15 / 100	15 ms	600 KiB

longesttrip

#include "longesttrip.h"

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

std::vector<int> longest_trip(int N, int D) {
        vector<int> a[2];
        a[0] = {0};
        int i = 1;
        for (; i < N; i++) {
                if (are_connected({a[0].back()}, {i})) {
                        a[0].emplace_back(i);
                } else {
                        a[1].emplace_back(i++);
                        break;
                }
        }
        bool merge = 0;
        bool ask = 0;
        int last_merge_pos = -1;
        for (; i < N; i++) {
                int x = a[0].back();
                int y = a[1].back();
                if (merge) {
                        assert(a[1].back() == i - 1);
                        if (are_connected({i - 1}, {i})) {
                                a[1].emplace_back(i);
                        } else {
                                a[0].insert(a[0].begin() + last_merge_pos, i);
                        }
                        merge = 0;
                } else if (are_connected({i}, {x})) {
                        a[0].emplace_back(i);
                } else {
                        if (ask) {
                                a[1].emplace_back(i);
                                ask = 0;
                        } else {
                                if (are_connected({i}, {y})) {
                                        a[1].emplace_back(i);
                                        ask = 1;
                                } else {
                                        last_merge_pos = a[0].size();
                                        merge = 1;
                                        while (a[1].size()) a[0].emplace_back(a[1].back()), a[1].pop_back();
                                        a[1].emplace_back(i);
                                }
                        }
                }
        }
        if (a[0].size() == N) return a[0];
        assert(a[0].size() + a[1].size() == N);
        int x = a[0][0], y = a[0].back();
        int z = a[1][0], t = a[1].back();
        auto join = [&](int p, int q) {
                if (p) reverse(a[0].begin(), a[0].end());
                if (q) reverse(a[1].begin(), a[1].end());
                a[0].insert(a[0].end(), a[1].begin(), a[1].end());
                return a[0];
        };
        if (are_connected({x}, {z})) {
                return join(1, 0);
        } else if (are_connected({x}, {t})) {
                return join(1, 1);
        } else if (are_connected({y}, {z})) {
                return join(0, 0);
        } else if (are_connected({y}, {t})) {
                return join(0, 1);
        } else {
                int l1 = 0, r1 = a[0].size();
                int l2 = 0, r2 = a[1].size();
                auto ask = [&](int x, int y, int z, int t) {
                        vector<int> p, q;
                        for (int i = x; i < y; i++) p.emplace_back(a[0][i]);
                        for (int i = z; i < t; i++) q.emplace_back(a[1][i]);
                        if (p.size() && q.size()) return are_connected(p, q);
                        return false;
                };
                if (!ask(l1, r1, l2, r2)) {
                        if (a[0].size() < a[1].size()) swap(a[0], a[1]);
                        return a[0];
                } else {
                        while (l1 + 1 < r1) {
                                int m = l1 + r1 >> 1;
                                if (ask(l1, m, l2, r2)) {
                                        r1 = m;
                                } else {
                                        l1 = m;
                                }
                        }
                        while (l2 + 1 < r2) {
                                int m = l2 + r2 >> 1;
                                if (ask(l1, r1, l2, m)) {
                                        r2 = m;
                                } else {
                                        l2 = m;
                                }
                        }
                        assert(l1 + 1 == r1 && l2 + 1 == r2);
                        vector<int> ans;
                        for (int i = r1; i < a[0].size(); i++) ans.emplace_back(a[0][i]);
                        for (int i = 0; i < r1; i++) ans.emplace_back(a[0][i]);
                        for (int i = l2; i < a[1].size(); i++) ans.emplace_back(a[1][i]);
                        for (int i = 0; i < l2; i++) ans.emplace_back(a[1][i]);
                        return ans;
                }
        }
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:52:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |         if (a[0].size() == N) return a[0];
      |             ~~~~~~~~~~~~^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from longesttrip.cpp:4:
longesttrip.cpp:53:42: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |         assert(a[0].size() + a[1].size() == N);
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
longesttrip.cpp:85:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |                                 int m = l1 + r1 >> 1;
      |                                         ~~~^~~~
longesttrip.cpp:93:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |                                 int m = l2 + r2 >> 1;
      |                                         ~~~^~~~
longesttrip.cpp:102:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |                         for (int i = r1; i < a[0].size(); i++) ans.emplace_back(a[0][i]);
      |                                          ~~^~~~~~~~~~~~~
longesttrip.cpp:104:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |                         for (int i = l2; i < a[1].size(); i++) ans.emplace_back(a[1][i]);
      |                                          ~~^~~~~~~~~~~~~

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