oj.uz

Submission #1038502

# Submission time Handle Problem Language Result Execution time Memory
1038502 2024-07-29T21:28:50 Z erray Longest Trip (IOI23_longesttrip) C++17
15 / 100
 16 ms 692 KB 
    #include "longesttrip.h"
    #include <bits/stdc++.h>
     
    using namespace std;
     
    #ifdef DEBUG 
      #include "/home/ioi/egoi2024/d2/debug.h"
    #else 
      #define debug(...) void(37)
    #endif
     
    vector<int> m(vector<int> x, vector<int> y) {
      vector<int> res;
      res = x;
      res.insert(res.end(), y.begin(), y.end());
      return res;
    }
     
     
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
     
    std::vector<int> longest_trip(int N, int D) {
      array<vector<int>, 2> l;
      l[0] = {0}; l[1] = {1};
      bool dis = false;
      for (int i = 2; i < N; ++i) {
        if (are_connected({i}, {l[0].back()})) {
          l[0].push_back(i);
          dis = false;
        } else if (dis) {
          l[1].push_back(i);
          dis = false;
        } else if (are_connected({i}, {l[1].back()})) {
          l[1].push_back(i);
          dis = true;
        } else {
          l[0] = m(l[0], vector<int>(l[1].rbegin(), l[1].rend()));
          dis = int(l[1].size()) == 1;
          l[1] = {i};
        }
      } 
      debug(l);
      if (!are_connected(l[0], l[1])) {
        return  int(l[0].size()) > int(l[1].size()) ? l[0] : l[1];
      }
      vector<int> fe0, fe1;
      int l0 = int(l[0].size());
      int l1 = int(l[1].size());
      for (int i = 0; i < l0; ++i) {
        if (i == 0 || i == l0 - 1) fe0.push_back(l[0][i]);
      }
      for (int i = 0; i < l1; ++i) {
        if (i == 0 || i == l1 - 1) fe1.push_back(l[1][i]);
      }
      if (!are_connected(fe0, fe1)) {
        int s = -1;
        {
          int low = 0, high = int(l[1].size()) - 1;
          while (low < high) {
            int mid = (low + high) >> 1;
            if (are_connected(l[0], vector<int>(l[1].begin(), l[1].begin() + mid + 1))) {
              high = mid;
            } else {
              low = mid + 1;
            }
          }
          s = low;
        }
        int f = -1;
        {
          int low = 0, high = int(l[0].size()) - 1;
          while (low < high) {
            int mid = (low + high) >> 1;
            if (are_connected({l[1][s]}, vector<int>(l[0].begin(), l[0].begin() + mid + 1))) {
              high = mid;
            } else {
              low = mid + 1;
            }
          }
          f = low;
        }
        rotate(l[1].begin(), l[1].begin() + s, l[1].end());
        if (f != int(l[0].size()) - 1) rotate(l[0].begin(), l[0].begin() + f + 1, l[0].end());
        vector<int> ans = m(l[0], l[1]);
        return ans;
      }
      vector<int> ans;
      for (int it = 0; it < 2; ++it) {
        for (int it1 = 0; it1 < 2; it1++) {
          if (are_connected({l[0].back()}, {l[1][0]})) {
            ans = m(l[0], l[1]);
          }
          reverse(l[1].begin(), l[1].end());
        }
        swap(l[0], l[1]);
      }
      return ans;
    }

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 16 ms 344 KB Output is correct
2 Correct 12 ms 348 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 6 ms 444 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 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 6 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 14 ms 344 KB Output is correct
7 Correct 7 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 7 ms 444 KB Output is correct
10 Correct 5 ms 344 KB Output is correct
11 Correct 5 ms 344 KB Output is correct
12 Correct 7 ms 344 KB Output is correct
13 Correct 7 ms 344 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 344 KB Output is correct
2 Correct 7 ms 344 KB Output is correct
3 Correct 7 ms 344 KB Output is correct
4 Correct 6 ms 440 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 13 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 6 ms 600 KB Output is correct
10 Correct 6 ms 448 KB Output is correct
11 Correct 5 ms 344 KB Output is correct
12 Correct 7 ms 440 KB Output is correct
13 Correct 4 ms 344 KB Output is correct
14 Correct 8 ms 344 KB Output is correct
15 Correct 9 ms 344 KB Output is correct
16 Incorrect 5 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 344 KB Output is correct
2 Correct 11 ms 344 KB Output is correct
3 Correct 6 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 7 ms 344 KB Output is correct
6 Correct 13 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 6 ms 344 KB Output is correct
10 Correct 6 ms 344 KB Output is correct
11 Correct 8 ms 692 KB Output is correct
12 Correct 5 ms 344 KB Output is correct
13 Correct 5 ms 444 KB Output is correct
14 Correct 5 ms 344 KB Output is correct
15 Correct 7 ms 344 KB Output is correct
16 Incorrect 8 ms 344 KB Incorrect
17 Halted 0 ms 0 KB -