184782025-10-23 18:56:42ubormaciÜltetéscpp17Részben helyes 37.5/75456ms1004 KiB
#include <iostream>
#include <algorithm> // for sort, mainly
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <array>
#include <string>
#include <cstdio>
#include <iterator>
#include <unordered_set>
#include <cstdint> // for int64_t, int32_t, etc
#include <queue>
#include <stack>
#include <deque>
#include <numeric> // gcd, lcm
#include <fstream>
#include <bitset> // for bitset
#include <iomanip>
#include <cassert> // for set with custom ordering
#include <type_traits> // for set with custom ordering
#include <utility> // for swap, forward, etc
using namespace std;

#pragma GCC optimize("O2")
// #pragma GCC optimize("O1","O2","O3","Ofast","unroll-loops")
// #pragma GCC target("sse","sse2","sse3","sse4.1","sse4.2","avx","avx2","fma")

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

/*

notes:

int64_t
stoi(string s) -> string to int
to_string() -> int (or else) to string

vector declaration:
vector<ll> v(n, 0)
vector<vector<ll>> v(n, vector<ll>(n, 0));

{if statement} ? {truth value} : {false value}

#ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif

std::lcm(ll a, ll b), std::gcd(int a, int b)

cout << fixed << setprecision(n);

set with custom ordering
set<ll, decltype(&cmp)> qu(cmp);

*/

typedef int64_t ll;

vector<ll> to;

ll dfs(ll i, vector<bool> &vis) {

	vis[i] = true;

	if(vis[to[i]] == false) {
		return 1 + dfs(to[i], vis);
	}else{
		return 0;
	}

}
 
void solve() {

	ll n;
	cin >> n;
	to.resize(n+1, 0);
	vector<ll> ind(n+1, 0);
	for(ll i = 1; i <= n; i++) {
		cin >> to[i];
		ind[to[i]]++;
	}

	// v[i] <- kinek akar az i-edik sugni
	// i legyen v[i] mellett

	/*

	1 2 3 4 5 6 7 8
	3 1 4 1 1 7 8 6

	ez effektive egy graf

	*/

	vector<pair<ll,ll>> d(n, {0,0});

	for(ll i = 1; i <= n; i++) {

		vector<bool> vis(n+1, false);
		d[i-1] = {dfs(i, vis), i};

	}

	//cerr << "\nd=" << d;

	ll fin = 0;
	vector<ll> res;

	sort(d.rbegin(), d.rend());
	vector<bool> yet(n+1, false);
	for(const auto & [len, source] : d) {

		if(yet[source]) {
			continue;
		}

		yet[source] = true;

		ll actlen = 0;

		ll curr = source;
		res.push_back(curr);
		while(yet[to[curr]] == false) {
			yet[to[curr]] = true;
			curr = to[curr];
			res.push_back(curr);
			actlen++;
		}

		fin += actlen;
	}

	cout << fin << "\n";
	for(const auto & x : res) {
		cout << x << " ";
	}

	

}

int main()
{
	std::ios_base::sync_with_stdio(false);
	//cin.tie(nullptr);
	//cout.tie(nullptr);

	solve();

	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Részben helyes1ms316 KiB
2Részben helyes8ms688 KiB
subtask22.5/5
3Részben helyes1ms316 KiB
4Részben helyes1ms316 KiB
5Részben helyes1ms316 KiB
6Elfogadva1ms316 KiB
7Részben helyes1ms316 KiB
subtask32.5/5
8Részben helyes1ms316 KiB
9Részben helyes1ms316 KiB
10Részben helyes1ms316 KiB
11Részben helyes1ms548 KiB
12Részben helyes1ms360 KiB
subtask42.5/5
13Részben helyes1ms316 KiB
14Részben helyes1ms316 KiB
15Részben helyes1ms316 KiB
16Részben helyes1ms316 KiB
17Részben helyes1ms316 KiB
subtask55/10
18Részben helyes1ms512 KiB
19Részben helyes4ms316 KiB
20Részben helyes4ms316 KiB
21Részben helyes4ms316 KiB
22Részben helyes4ms316 KiB
23Részben helyes1ms316 KiB
24Részben helyes1ms316 KiB
25Részben helyes4ms316 KiB
26Részben helyes442ms1004 KiB
27Részben helyes456ms1004 KiB
subtask65/10
28Részben helyes6ms316 KiB
29Részben helyes10ms316 KiB
30Részben helyes29ms564 KiB
31Részben helyes76ms548 KiB
32Részben helyes72ms576 KiB
33Részben helyes123ms604 KiB
34Részben helyes122ms612 KiB
35Részben helyes232ms564 KiB
36Részben helyes354ms840 KiB
37Részben helyes303ms756 KiB
subtask720/40
38Részben helyes2ms316 KiB
39Részben helyes3ms316 KiB
40Részben helyes3ms564 KiB
41Részben helyes4ms572 KiB
42Részben helyes4ms648 KiB
43Részben helyes4ms612 KiB
44Részben helyes8ms648 KiB
45Részben helyes8ms832 KiB
46Részben helyes10ms716 KiB
47Részben helyes13ms996 KiB
48Részben helyes12ms756 KiB
49Részben helyes8ms892 KiB
50Részben helyes9ms1004 KiB
51Részben helyes13ms752 KiB
52Részben helyes17ms756 KiB
53Részben helyes13ms756 KiB
54Részben helyes10ms820 KiB
55Részben helyes10ms836 KiB
56Részben helyes17ms756 KiB
57Részben helyes10ms820 KiB