Submission #1335675

#TimeUsernameProblemLanguageResultExecution timeMemory
1335675edl0231A String Problem (EGOI25_stringproblem)C++20
100 / 100
64 ms5464 KiB
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> ct;
int mx_ind = -1;
vector<bool> visited;
vector<int> nxt;
vector<int> v;
void dfs(int node)
{
    vector<int> order;
    visited[node] = true;
    while (true)
    {
        order.emplace_back(node);
        node = mx_ind - node;
        if (node < 0) node += N * 2;
        visited[node] = true;
        order.emplace_back(node);
        node = nxt[node];
        if (visited[node]) break;
        visited[node] = true;
    }
//    for (auto i : order) cout << i << ' ';
    for (int i = 1; i < (int)order.size(); i += 2)
    {
        cout << v[order[i]] << ' ' << nxt[order[i]] << ' ' << order[i - 1] << '\n';
    }
}
int main()
{
    cin >> N;
    v.resize(N * 2);
    ct.resize(N * 2);
    nxt.resize(N * 2);
    visited.resize(N * 2);
    for (int i = 0; i < N; i++)
    {
        int x, y;
        cin >> x >> y;
        if (x > y) swap(x, y);
        nxt[x] = y, nxt[y] = x;
        v[x] = i, v[y] = i;
        ct[(x + y) % (N * 2)]++;
    }
    int mx = -1;
    for (int i = 0; i < N * 2; i++)
    {
        if (!(i & 1)) continue;
        if (ct[i] > mx) {mx = ct[i], mx_ind = i;}
    }
    int ans = 0;
    for (int i = 0; i < N * 2; i++)
    {
        if ((i + nxt[i] - mx_ind) % (N * 2) == 0) visited[i] = true;
        else ans++;
    }
    cout << ans / 2 << '\n';
    for (int i = 0; i < N * 2; i++)
    {
        if (!visited[i]) dfs(i);
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...