Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- #include <set>
- #include <queue>
- #include <algorithm>
- #include <string>
- #include <cmath>
- #include <cstdio>
- #include <iomanip>
- #include <fstream>
- #include <cassert>
- #include <cstring>
- #include <unordered_set>
- #include <unordered_map>
- #include <numeric>
- #include <ctime>
- #include <bitset>
- #include <random>
- #include <complex>
- #include <random>
- #include <functional>
- using namespace std;
- void solve() {
- int n;
- cin >> n;
- vector<int> a(n + 1);
- vector<vector<int>> g(n + 1);
- for (int i = 1; i <= n; i++) {
- cin >> a[i];
- g[i].push_back(i - a[i]);
- }
- for (int i = 1; i <= n; i++) {
- if (a[i] == 0) {
- cout << 1 << '\n' << i << '\n';
- return;
- }
- }
- vector<int> used(n + 1);
- pair<int, int> rs = {-1, -1};
- function<void(int)> dfs = [&](int cur) {
- used[cur] = 1;
- for (auto t : g[cur]) {
- if (used[t] == 0) {
- dfs(t);
- }
- if (used[t] == 1) {
- rs = {cur, t};
- }
- }
- used[cur] = 2;
- };
- for (int i = 1; i <= n; i++) {
- if (used[i] == 0) {
- dfs(i);
- }
- }
- swap(rs.first, rs.second);
- fill(used.begin(), used.end(), 0);
- vector<int> p(n + 1);
- function<void(int, int)> dfs2 = [&](int cur, int pr) {
- used[cur] = 1;
- p[cur] = pr;
- for (auto t : g[cur]) {
- if (used[t] == 0) {
- dfs2(t, cur);
- }
- }
- used[cur] = 2;
- };
- dfs2(rs.first, -1);
- assert(used[rs.second]);
- vector<int> v = {rs.first};
- int cur = rs.second;
- while (cur != rs.first) {
- v.push_back(cur);
- cur = p[cur];
- }
- cout << v.size() << '\n';
- for (auto t : v) {
- cout << t << ' ';
- }
- cout << '\n';
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- int q;
- cin >> q;
- while (q--) {
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement