oj.uz

답안 #845799

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
845799 2023-09-06T15:46:48 Z vjudge1 가장 긴 여행 (IOI23_longesttrip) C++17
15 / 100
 15 ms 600 KB 
#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

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 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 344 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 4 ms 344 KB Output is correct
5 Correct 5 ms 600 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 4 ms 344 KB Output is correct
10 Correct 4 ms 344 KB Output is correct
11 Correct 4 ms 344 KB Output is correct
12 Correct 5 ms 344 KB Output is correct
13 Correct 4 ms 344 KB Output is correct

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 4 ms 344 KB Output is correct
10 Correct 5 ms 344 KB Output is correct
11 Correct 5 ms 600 KB Output is correct
12 Correct 4 ms 344 KB Output is correct
13 Correct 5 ms 344 KB Output is correct
14 Correct 14 ms 344 KB Output is correct
15 Incorrect 5 ms 344 KB Incorrect
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 4 ms 496 KB Output is correct
11 Correct 5 ms 540 KB Output is correct
12 Correct 4 ms 344 KB Output is correct
13 Correct 4 ms 344 KB Output is correct
14 Correct 15 ms 344 KB Output is correct
15 Incorrect 7 ms 344 KB Incorrect
16 Halted 0 ms 0 KB -