oj.uz

Submission #997177

# Submission time Handle Problem Language Result Execution time Memory
997177 2024-06-11T19:15:34 Z kunzaZa183 Longest Trip (IOI23_longesttrip) C++17
100 / 100
 12 ms 640 KB 
#include "longesttrip.h"

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

vector<int> longest_trip(int N, int D) {
  vector<int> trip1(1, 0), trip2(1, 1);

  int state = 2;
  int num1;

  for (int i = 2; i < N; i++) {
    if (state == 0) {
      if (are_connected(vector<int>(1, trip2.front()), vector<int>(1, i)))
        trip2.push_back(i);
      else
        trip1.insert(trip1.begin() + num1, i);
      state = 2;
    } else if (state == 1) {
      if (are_connected(vector<int>(1, trip1.back()), vector<int>(1, i)))
        trip1.push_back(i);
      else
        trip2.push_back(i);
      state = 2;
    } else if (state == 2) {
      bool b1 = are_connected(vector<int>(1, trip1.back()), vector<int>(1, i)),
           b2 = are_connected(vector<int>(1, trip2.back()), vector<int>(1, i));
      if (b1 && b2) {
        reverse(trip2.begin(), trip2.end());
        trip1.push_back(i);
        for (auto a : trip2) trip1.push_back(a);
        trip2.clear();
        if (i == N - 1) return trip1;
        i++;
        trip2.push_back(i);
      } else if (b1) {
        trip1.push_back(i);
        state = 1;
      } else if (b2) {
        trip2.push_back(i);
        state = 1;
      } else {
        num1 = trip1.size();
        reverse(trip2.begin(), trip2.end());
        for (auto a : trip2) trip1.push_back(a);
        trip2.clear();
        trip2.push_back(i);
        state = 0;
      }
    }
  }

  if (trip2.empty()) return trip1;
  if (are_connected(trip1, trip2)) {
    // vector<int> vi, vi2;
    // if (trip1.size() != 1)
    //   vi.push_back(trip1.front()), vi.push_back(trip1.back());
    // else
    //   vi.push_back(trip1.front());
    // if (trip2.size() != 1)
    //   vi2.push_back(trip2.front()), vi2.push_back(trip2.back());
    // else
    //   vi2.push_back(trip2.front());
    // if (are_connected(vi, vi2)) {
    //   while (1) {
    //   }
    // }

    // if (trip1.size() != 1) {
    //   if (!are_connected(vector<int>(1, trip1.front()),
    //                      vector<int>(1, trip1.back())))

    //     while (1) {
    //     }
    // }
    // if (trip2.size() != 1) {
    //   if (!are_connected(vector<int>(1, trip2.front()),
    //                      vector<int>(1, trip2.back())))

    //     while (1) {
    //     }
    // }

    vector<int> vi, vi2;
    if (trip1.size() != 1)
      vi.push_back(trip1.front()), vi.push_back(trip1.back());
    else
      vi.push_back(trip1.front());
    if (trip2.size() != 1)
      vi2.push_back(trip2.front()), vi2.push_back(trip2.back());
    else
      vi2.push_back(trip2.front());
    if (are_connected(vi, vi2)) {
      vector<int> ans;
      if (are_connected(vector<int>(1, trip1.front()),
                        vector<int>(1, trip2.front())))
        reverse(trip1.begin(), trip1.end());
      else if (are_connected(vector<int>(1, trip1.front()),
                             vector<int>(1, trip2.back())))
        trip1.swap(trip2);
      else if (are_connected(vector<int>(1, trip1.back()),
                             vector<int>(1, trip2.front()))) {
      } else if (are_connected(vector<int>(1, trip1.back()),
                               vector<int>(1, trip2.back())))
        reverse(trip2.begin(), trip2.end());

      for (auto a : trip1) ans.push_back(a);
      for (auto a : trip2) ans.push_back(a);
      return ans;
    }

    int l = 0, r = int(trip1.size()) - 1;
    while (l < r) {
      int mid = (l + r) / 2;
      vector<int> tmp;
      for (int i = l; i <= mid; i++) tmp.push_back(trip1[i]);
      if (are_connected(tmp, trip2))
        r = mid;
      else
        l = mid + 1;
    }
    int firstone = l;
    l = 0, r = int(trip2.size()) - 1;
    while (l < r) {
      int mid = (l + r) / 2;
      vector<int> tmp;
      for (int i = l; i <= mid; i++) tmp.push_back(trip2[i]);
      if (are_connected(tmp, vector<int>(1, trip1[firstone])))
        r = mid;
      else
        l = mid + 1;
    }
    int secondone = l;
    vector<int> ans;
    for (int i = firstone + 1; i < trip1.size(); i++) ans.push_back(trip1[i]);
    for (int i = 0; i <= firstone; i++) ans.push_back(trip1[i]);
    for (int i = secondone; i < trip2.size(); i++) ans.push_back(trip2[i]);
    for (int i = 0; i < secondone; i++) ans.push_back(trip2[i]);
    return ans;
  }

  if (trip1.size() < trip2.size()) trip1.swap(trip2);
  return trip1;
}

Compilation message

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:135:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for (int i = firstone + 1; i < trip1.size(); i++) ans.push_back(trip1[i]);
      |                                ~~^~~~~~~~~~~~~~
longesttrip.cpp:137:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     for (int i = secondone; i < trip2.size(); i++) ans.push_back(trip2[i]);
      |                             ~~^~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 8 ms 344 KB Output is correct
3 Correct 6 ms 344 KB Output is correct
4 Correct 6 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 7 ms 344 KB Output is correct
5 Correct 8 ms 344 KB Output is correct
6 Correct 9 ms 372 KB Output is correct
7 Correct 8 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 5 ms 344 KB Output is correct
11 Correct 6 ms 344 KB Output is correct
12 Correct 8 ms 424 KB Output is correct
13 Correct 4 ms 344 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Correct 8 ms 344 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 6 ms 344 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 6 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 7 ms 344 KB Output is correct
10 Correct 7 ms 344 KB Output is correct
11 Correct 8 ms 344 KB Output is correct
12 Correct 5 ms 344 KB Output is correct
13 Correct 5 ms 344 KB Output is correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 7 ms 344 KB Output is correct
16 Correct 6 ms 344 KB Output is correct
17 Correct 5 ms 344 KB Output is correct
18 Correct 6 ms 344 KB Output is correct
19 Correct 7 ms 344 KB Output is correct
20 Correct 8 ms 344 KB Output is correct
21 Correct 7 ms 344 KB Output is correct
22 Correct 6 ms 344 KB Output is correct
23 Correct 6 ms 424 KB Output is correct
24 Correct 4 ms 344 KB Output is correct
25 Correct 4 ms 344 KB Output is correct
26 Correct 6 ms 344 KB Output is correct
27 Correct 6 ms 344 KB Output is correct
28 Correct 6 ms 344 KB Output is correct
29 Correct 7 ms 344 KB Output is correct
30 Correct 6 ms 344 KB Output is correct
31 Correct 11 ms 344 KB Output is correct
32 Correct 7 ms 344 KB Output is correct
33 Correct 10 ms 344 KB Output is correct
34 Correct 7 ms 344 KB Output is correct
35 Correct 7 ms 344 KB Output is correct
36 Correct 6 ms 344 KB Output is correct
37 Correct 7 ms 344 KB Output is correct
38 Correct 7 ms 344 KB Output is correct
39 Correct 11 ms 344 KB Output is correct
40 Correct 6 ms 344 KB Output is correct
41 Correct 7 ms 344 KB Output is correct
42 Correct 6 ms 344 KB Output is correct
43 Correct 7 ms 344 KB Output is correct
44 Correct 5 ms 344 KB Output is correct
45 Correct 9 ms 344 KB Output is correct
46 Correct 10 ms 344 KB Output is correct
47 Correct 9 ms 344 KB Output is correct
48 Correct 12 ms 344 KB Output is correct
49 Correct 6 ms 344 KB Output is correct
50 Correct 6 ms 344 KB Output is correct
51 Correct 8 ms 344 KB Output is correct
52 Correct 8 ms 344 KB Output is correct
53 Correct 6 ms 344 KB Output is correct
54 Correct 9 ms 344 KB Output is correct
55 Correct 7 ms 344 KB Output is correct
56 Correct 5 ms 344 KB Output is correct
57 Correct 8 ms 344 KB Output is correct
58 Correct 12 ms 344 KB Output is correct
59 Correct 8 ms 344 KB Output is correct
60 Correct 8 ms 344 KB Output is correct
61 Correct 9 ms 436 KB Output is correct
62 Correct 8 ms 344 KB Output is correct
63 Correct 8 ms 432 KB Output is correct
64 Correct 11 ms 344 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 9 ms 344 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 6 ms 340 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 8 ms 344 KB Output is correct
8 Correct 6 ms 344 KB Output is correct
9 Correct 7 ms 344 KB Output is correct
10 Correct 5 ms 344 KB Output is correct
11 Correct 6 ms 344 KB Output is correct
12 Correct 4 ms 344 KB Output is correct
13 Correct 5 ms 436 KB Output is correct
14 Correct 6 ms 344 KB Output is correct
15 Correct 5 ms 344 KB Output is correct
16 Correct 7 ms 344 KB Output is correct
17 Correct 9 ms 344 KB Output is correct
18 Correct 6 ms 344 KB Output is correct
19 Correct 6 ms 344 KB Output is correct
20 Correct 6 ms 600 KB Output is correct
21 Correct 6 ms 344 KB Output is correct
22 Correct 6 ms 344 KB Output is correct
23 Correct 6 ms 340 KB Output is correct
24 Correct 7 ms 344 KB Output is correct
25 Correct 6 ms 344 KB Output is correct
26 Correct 6 ms 344 KB Output is correct
27 Correct 7 ms 344 KB Output is correct
28 Correct 5 ms 344 KB Output is correct
29 Correct 7 ms 344 KB Output is correct
30 Correct 10 ms 344 KB Output is correct
31 Correct 7 ms 344 KB Output is correct
32 Correct 7 ms 344 KB Output is correct
33 Correct 9 ms 344 KB Output is correct
34 Correct 8 ms 344 KB Output is correct
35 Correct 7 ms 344 KB Output is correct
36 Correct 7 ms 344 KB Output is correct
37 Correct 6 ms 344 KB Output is correct
38 Correct 8 ms 344 KB Output is correct
39 Correct 8 ms 344 KB Output is correct
40 Correct 7 ms 600 KB Output is correct
41 Correct 7 ms 344 KB Output is correct
42 Correct 8 ms 344 KB Output is correct
43 Correct 4 ms 344 KB Output is correct
44 Correct 7 ms 344 KB Output is correct
45 Correct 6 ms 344 KB Output is correct
46 Correct 6 ms 344 KB Output is correct
47 Correct 9 ms 640 KB Output is correct
48 Correct 9 ms 600 KB Output is correct
49 Correct 7 ms 344 KB Output is correct
50 Correct 10 ms 344 KB Output is correct
51 Correct 7 ms 436 KB Output is correct
52 Correct 7 ms 344 KB Output is correct
53 Correct 7 ms 344 KB Output is correct
54 Correct 7 ms 344 KB Output is correct
55 Correct 6 ms 344 KB Output is correct
56 Correct 5 ms 344 KB Output is correct
57 Correct 8 ms 344 KB Output is correct
58 Correct 7 ms 428 KB Output is correct
59 Correct 5 ms 344 KB Output is correct
60 Correct 8 ms 344 KB Output is correct
61 Correct 7 ms 340 KB Output is correct
62 Correct 6 ms 344 KB Output is correct
63 Correct 8 ms 440 KB Output is correct
64 Correct 11 ms 344 KB Output is correct
65 Correct 8 ms 436 KB Output is correct
66 Correct 8 ms 344 KB Output is correct
67 Correct 7 ms 440 KB Output is correct
68 Correct 11 ms 344 KB Output is correct
69 Correct 7 ms 344 KB Output is correct
70 Correct 7 ms 344 KB Output is correct
71 Correct 11 ms 344 KB Output is correct
72 Correct 8 ms 344 KB Output is correct
73 Correct 7 ms 344 KB Output is correct
74 Correct 6 ms 344 KB Output is correct
75 Correct 5 ms 344 KB Output is correct
76 Correct 8 ms 344 KB Output is correct
77 Correct 9 ms 344 KB Output is correct
78 Correct 8 ms 344 KB Output is correct
79 Correct 11 ms 344 KB Output is correct
80 Correct 9 ms 344 KB Output is correct
81 Correct 7 ms 344 KB Output is correct
82 Correct 8 ms 600 KB Output is correct