184792025-10-23 19:17:38ubormaciÜltetéscpp17Partially correct 37.5/75456ms956 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) {

		//cerr << "\nsource=" << source;

		if(yet[source]) {
			//cerr << "\nskipped";
			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];
			//cerr << "\ncurr=" << curr;
			res.push_back(curr);
			actlen++;
		}

		//cerr << "\nstartlen=" << len;
		//cerr << "\nactlen=" << actlen;

		fin += actlen;
	}

	cout << fin << "\n";
	for(ll i = 0; i < res.size(); i++) {
		cout << res[i];
		if(i < res.size() - 1) {
			cout << " ";
		}
	}

	

}

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

	solve();

	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Partially correct1ms316 KiB
2Partially correct8ms820 KiB
subtask22.5/5
3Partially correct1ms316 KiB
4Partially correct1ms328 KiB
5Partially correct1ms316 KiB
6Accepted1ms316 KiB
7Partially correct1ms316 KiB
subtask32.5/5
8Partially correct1ms316 KiB
9Partially correct1ms316 KiB
10Partially correct1ms316 KiB
11Partially correct1ms316 KiB
12Partially correct1ms316 KiB
subtask42.5/5
13Partially correct1ms316 KiB
14Partially correct1ms316 KiB
15Partially correct1ms552 KiB
16Partially correct1ms316 KiB
17Partially correct1ms316 KiB
subtask55/10
18Partially correct1ms316 KiB
19Partially correct4ms460 KiB
20Partially correct4ms316 KiB
21Partially correct4ms316 KiB
22Partially correct4ms316 KiB
23Partially correct1ms316 KiB
24Partially correct1ms316 KiB
25Partially correct4ms508 KiB
26Partially correct439ms748 KiB
27Partially correct456ms820 KiB
subtask65/10
28Partially correct6ms316 KiB
29Partially correct10ms316 KiB
30Partially correct30ms564 KiB
31Partially correct79ms568 KiB
32Partially correct74ms564 KiB
33Partially correct123ms604 KiB
34Partially correct122ms616 KiB
35Partially correct233ms564 KiB
36Partially correct358ms752 KiB
37Partially correct301ms748 KiB
subtask720/40
38Partially correct2ms316 KiB
39Partially correct3ms508 KiB
40Partially correct3ms568 KiB
41Partially correct4ms564 KiB
42Partially correct4ms564 KiB
43Partially correct4ms564 KiB
44Partially correct8ms792 KiB
45Partially correct8ms820 KiB
46Partially correct10ms820 KiB
47Partially correct13ms820 KiB
48Partially correct12ms756 KiB
49Partially correct8ms956 KiB
50Partially correct9ms832 KiB
51Partially correct13ms756 KiB
52Partially correct17ms820 KiB
53Partially correct13ms820 KiB
54Partially correct10ms832 KiB
55Partially correct10ms756 KiB
56Partially correct17ms752 KiB
57Partially correct9ms820 KiB