184792025-10-23 19:17:38ubormaciÜltetéscpp17Részben helyes 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Részben helyes1ms316 KiB
2Részben helyes8ms820 KiB
subtask22.5/5
3Részben helyes1ms316 KiB
4Részben helyes1ms328 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 helyes1ms316 KiB
12Részben helyes1ms316 KiB
subtask42.5/5
13Részben helyes1ms316 KiB
14Részben helyes1ms316 KiB
15Részben helyes1ms552 KiB
16Részben helyes1ms316 KiB
17Részben helyes1ms316 KiB
subtask55/10
18Részben helyes1ms316 KiB
19Részben helyes4ms460 KiB
20Részben helyes4ms316 KiB
21Részben helyes4ms316 KiB
22Részben helyes4ms316 KiB
23Részben helyes1ms316 KiB
24Részben helyes1ms316 KiB
25Részben helyes4ms508 KiB
26Részben helyes439ms748 KiB
27Részben helyes456ms820 KiB
subtask65/10
28Részben helyes6ms316 KiB
29Részben helyes10ms316 KiB
30Részben helyes30ms564 KiB
31Részben helyes79ms568 KiB
32Részben helyes74ms564 KiB
33Részben helyes123ms604 KiB
34Részben helyes122ms616 KiB
35Részben helyes233ms564 KiB
36Részben helyes358ms752 KiB
37Részben helyes301ms748 KiB
subtask720/40
38Részben helyes2ms316 KiB
39Részben helyes3ms508 KiB
40Részben helyes3ms568 KiB
41Részben helyes4ms564 KiB
42Részben helyes4ms564 KiB
43Részben helyes4ms564 KiB
44Részben helyes8ms792 KiB
45Részben helyes8ms820 KiB
46Részben helyes10ms820 KiB
47Részben helyes13ms820 KiB
48Részben helyes12ms756 KiB
49Részben helyes8ms956 KiB
50Részben helyes9ms832 KiB
51Részben helyes13ms756 KiB
52Részben helyes17ms820 KiB
53Részben helyes13ms820 KiB
54Részben helyes10ms832 KiB
55Részben helyes10ms756 KiB
56Részben helyes17ms752 KiB
57Részben helyes9ms820 KiB