제출 #1336530

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1336530		limits	가장 긴 여행 (IOI23_longesttrip)	C++20	15 / 100	4 ms	432 KiB

longesttrip

#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define f0r(i, n) for (auto i = 0; i < (n); ++i)
#define fnr(i, n, k) for (auto i = (n); i < (k); ++i)
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define F first
#define S second
#define ctn(x) cout << x << '\n'
#define forl(a, l) for (auto a : l)
#define ctl(l) for (auto &a : (l)) cout << a << ' '; cout << endl;
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define ub(v, x) (upper_bound(all(v), x) - begin(v))
#define pq priority_queue

template <class T>
using V = vector<T>;
using ll = long long;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int, int>;
using ti = tuple<int, int, int>;
using Adj = V<vi>;
using vvi = V<vi>;

#include "longesttrip.h"

std::vector<int> longest_trip(int N, int D)
{
	if (D == 3) {
		vi A(N);
		iota(all(A), 0);
		return A;
	}
	if (D == 2) {
		vi A;
		A.pb(0);
		set<int> res;
		fnr(i, 1, N) res.insert(i);
		while (res.size() >= 2) {
			int x = *res.begin(), y = *next(res.begin());
			A.pb(are_connected({A.back()}, {x}) ? x : y);
			res.erase(A.back());
		}
		int x = *res.begin();
		if (are_connected({ A.back() }, {x})) A.pb(x);
		else {
			reverse(all(A));
			A.pb(x);
		}
		return A;
	}
	vi idx(N);
	iota(all(idx), 0);
	srand(time(0));
	random_shuffle(all(idx));
	vi A{0}, B{1};
	fnr(i, 2, N) {
		if (are_connected({i}, {A.back()})) {
			A.pb(i);
		} else if (are_connected({i}, {B.back()})) {
			B.pb(i);
		} else {
			A.insert(A.end(), all(B));
			B = {i};
		}
	}
	return A.size() > B.size() ? A : B;
}

컴파일 시 표준 에러 (stderr) 메시지

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:61:23: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<int*, vector<int> >]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   61 |         random_shuffle(all(idx));
      |         ~~~~~~~~~~~~~~^~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from longesttrip.cpp:4:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~

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