Submission #10,801

2024-04-14 11:48:15

cpp17

Accepted 100/100

649ms

66356 KiB

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

map<int, vector<int>> csucsok;
map<int, bool> bejart;
map<int, bool> bejart2;
vector<pii> ans;
vector<int> alap;

int legK(int akt){
    bejart[akt] = 1;
    int mini = akt;

    for(int x : csucsok[akt]){
        if(bejart[x]) continue;

        mini = min(mini, legK(x));
    }

    return mini;
}

void dfs(int akt, int mini){
    bejart2[akt] = 1;
    if(akt != mini){
        ans.push_back({akt, mini});
    }

    for(int x : csucsok[akt]){
        if(bejart2[x]) continue;

        dfs(x, mini);
    }
}

int main()
{
    int n;
    cin >> n;

    alap.assign(n, 0);
    for(int &x : alap){
        cin >> x;
        x--;
    }

    for(int i = 0; i < n / 2 + (n % 2); i++){
        if(alap[i] != alap[n - 1 - i]){
            csucsok[alap[i]].push_back(alap[n - 1 - i]);
            csucsok[alap[n - 1 - i]].push_back(alap[i]);
        }
    }

    for(auto &x : csucsok){
        if(bejart[x.first]) continue;

        int a = legK(x.first);
        dfs(x.first, a);
    }

    cout << ans.size() << "\n";
    for(pii x : ans){
        cout << x.first + 1 << " " << x.second + 1 << "\n";
    }
}

	Sum	Test	Verdict	Time	Memory
subtask1	0/0
		1	Accepted	3ms	1748 KiB
		2	Accepted	212ms	24704 KiB
subtask2	9/9
		3	Accepted	3ms	2252 KiB
		4	Accepted	3ms	2352 KiB
		5	Accepted	3ms	2568 KiB
		6	Accepted	3ms	2784 KiB
		7	Accepted	3ms	2868 KiB
subtask3	14/14
		8	Accepted	3ms	2920 KiB
		9	Accepted	3ms	2920 KiB
		10	Accepted	3ms	2916 KiB
		11	Accepted	3ms	3044 KiB
		12	Accepted	3ms	3052 KiB
		13	Accepted	3ms	3300 KiB
subtask4	25/25
		14	Accepted	3ms	3528 KiB
		15	Accepted	4ms	3796 KiB
		16	Accepted	6ms	4128 KiB
		17	Accepted	7ms	4292 KiB
		18	Accepted	6ms	4028 KiB
		19	Accepted	6ms	3828 KiB
		20	Accepted	6ms	4080 KiB
		21	Accepted	4ms	3796 KiB
subtask5	22/22
		22	Accepted	352ms	46540 KiB
		23	Accepted	337ms	66104 KiB
		24	Accepted	328ms	66356 KiB
		25	Accepted	337ms	46796 KiB
		26	Accepted	301ms	46768 KiB
		27	Accepted	286ms	64204 KiB
		28	Accepted	293ms	64104 KiB
		29	Accepted	305ms	46680 KiB
		30	Accepted	275ms	46668 KiB
		31	Accepted	275ms	65560 KiB
		32	Accepted	272ms	65636 KiB
		33	Accepted	264ms	46668 KiB
		34	Accepted	284ms	46780 KiB
		35	Accepted	287ms	54624 KiB
		36	Accepted	296ms	60660 KiB
		37	Accepted	268ms	46780 KiB
subtask6	30/30
		38	Accepted	3ms	4060 KiB
		39	Accepted	209ms	26896 KiB
		40	Accepted	3ms	2252 KiB
		41	Accepted	3ms	2352 KiB
		42	Accepted	3ms	2568 KiB
		43	Accepted	3ms	2784 KiB
		44	Accepted	3ms	2868 KiB
		45	Accepted	3ms	2920 KiB
		46	Accepted	3ms	2920 KiB
		47	Accepted	3ms	2916 KiB
		48	Accepted	3ms	3044 KiB
		49	Accepted	3ms	3052 KiB
		50	Accepted	3ms	3300 KiB
		51	Accepted	3ms	3528 KiB
		52	Accepted	4ms	3796 KiB
		53	Accepted	6ms	4128 KiB
		54	Accepted	7ms	4292 KiB
		55	Accepted	6ms	4028 KiB
		56	Accepted	6ms	3828 KiB
		57	Accepted	6ms	4080 KiB
		58	Accepted	4ms	3796 KiB
		59	Accepted	352ms	46540 KiB
		60	Accepted	337ms	66104 KiB
		61	Accepted	328ms	66356 KiB
		62	Accepted	337ms	46796 KiB
		63	Accepted	301ms	46768 KiB
		64	Accepted	286ms	64204 KiB
		65	Accepted	293ms	64104 KiB
		66	Accepted	305ms	46680 KiB
		67	Accepted	275ms	46668 KiB
		68	Accepted	275ms	65560 KiB
		69	Accepted	272ms	65636 KiB
		70	Accepted	264ms	46668 KiB
		71	Accepted	284ms	46780 KiB
		72	Accepted	287ms	54624 KiB
		73	Accepted	296ms	60660 KiB
		74	Accepted	268ms	46780 KiB
		75	Accepted	642ms	58800 KiB
		76	Accepted	335ms	31760 KiB
		77	Accepted	129ms	13160 KiB
		78	Accepted	370ms	31496 KiB
		79	Accepted	218ms	16188 KiB
		80	Accepted	76ms	5664 KiB
		81	Accepted	78ms	5664 KiB
		82	Accepted	79ms	5660 KiB
		83	Accepted	649ms	59004 KiB
		84	Accepted	151ms	13380 KiB
		85	Accepted	244ms	16656 KiB
		86	Accepted	101ms	6200 KiB
		87	Accepted	100ms	6072 KiB
		88	Accepted	100ms	6160 KiB
		89	Accepted	103ms	6200 KiB