oj.uz

Submission #996325

# Submission time Handle Problem Language Result Execution time Memory
996325 2024-06-10T12:52:13 Z kunzaZa183 Longest Trip (IOI23_longesttrip) C++17
15 / 100
 17 ms 436 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;
  for (int i = 1; i < N; i++) {
    bool b = are_connected(vector<int>(1, trip1.front()), vector<int>(1, i)),
         b2 = are_connected(vector<int>(1, trip1.back()), vector<int>(1, i));
    if (!b && !b2)
      trip2.push_back(i);
    else if (trip2.empty()) {
      if (b)
        trip1.insert(trip1.begin(), i);
      else
        trip2.push_back(i);
    } else if (b) {
      bool b3 = are_connected(vector<int>(1, trip2.front()), vector<int>(1, i)),
           b4 = are_connected(vector<int>(1, trip2.back()), vector<int>(1, i));
      if (b3) {
        trip1.insert(trip1.begin(), i);
        for (auto a : trip2) trip1.insert(trip1.begin(), a);
        trip2.clear();
      } else if (b4) {
        trip2.push_back(i);
        for (auto a : trip1) trip2.push_back(a);
        trip1 = trip2;
        trip2.clear();
      } else {
        trip1.insert(trip1.begin(), i);
      }
    } else if (b2) {
      bool b3 = are_connected(vector<int>(1, trip2.front()), vector<int>(1, i)),
           b4 = are_connected(vector<int>(1, trip2.back()), vector<int>(1, i));
      if (b3) {
        trip1.push_back(i);
        for (auto a : trip2) trip1.push_back(a);
        trip2.clear();
      } else if (b4) {
        reverse(trip2.begin(), trip2.end());
        trip1.push_back(i);
        for (auto a : trip2) trip1.push_back(a);
        trip2.clear();
      } else {
        trip1.push_back(i);
      }
    }
  }
  if (trip2.empty()) return trip1;
  if (are_connected(trip1, trip2)) {
    if (trip1.size() != 1 && trip2.size() != 1) {
      vector<int> vi, vi2;
      vi.push_back(trip1.front()), vi.push_back(trip1.back());
      vi2.push_back(trip2.front()), vi2.push_back(trip2.back());
      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) {
      // }
    }

    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:99:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for (int i = firstone + 1; i < trip1.size(); i++) ans.push_back(trip1[i]);
      |                                ~~^~~~~~~~~~~~~~
longesttrip.cpp:101:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     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 3 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 9 ms 344 KB Output is correct
3 Correct 10 ms 344 KB Output is correct
4 Correct 9 ms 344 KB Output is correct
5 Correct 10 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 9 ms 344 KB Output is correct
3 Correct 10 ms 344 KB Output is correct
4 Correct 7 ms 344 KB Output is correct
5 Correct 7 ms 344 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 11 ms 344 KB Output is correct
8 Correct 10 ms 344 KB Output is correct
9 Correct 14 ms 344 KB Output is correct
10 Correct 10 ms 344 KB Output is correct
11 Correct 9 ms 344 KB Output is correct
12 Correct 14 ms 436 KB Output is correct
13 Correct 14 ms 344 KB Output is correct
14 Correct 7 ms 340 KB Output is correct
15 Correct 12 ms 344 KB Output is correct
16 Incorrect 1 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 10 ms 344 KB Output is correct
3 Correct 10 ms 344 KB Output is correct
4 Correct 10 ms 344 KB Output is correct
5 Partially correct 10 ms 344 KB Output is partially correct
6 Correct 17 ms 344 KB Output is correct
7 Correct 10 ms 344 KB Output is correct
8 Correct 8 ms 344 KB Output is correct
9 Correct 11 ms 344 KB Output is correct
10 Partially correct 8 ms 344 KB Output is partially correct
11 Partially correct 6 ms 344 KB Output is partially correct
12 Partially correct 10 ms 344 KB Output is partially correct
13 Partially correct 10 ms 344 KB Output is partially correct
14 Correct 8 ms 344 KB Output is correct
15 Correct 12 ms 344 KB Output is correct
16 Incorrect 1 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -