Submission #1364596

#TimeUsernameProblemLanguageResultExecution timeMemory
1364596shahaprogA String Problem (EGOI25_stringproblem)C++20
15 / 100
22 ms6776 KiB
#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;
    vector<pair<int, int>> initial(N);
    vector<int> count(2 * N, 0);
    for (int i = 0; i < N; ++i) {
        cin >> initial[i].first >> initial[i].second;
        count[(initial[i].first + initial[i].second) % (2 * N)]++;
    }

    int best_s = 0;
    for (int s = 0; s < 2 * N; ++s) {
        if (count[s] > count[best_s]) best_s = s;
    }

    vector<int> pin_to_string(2 * N);
    vector<pair<int, int>> current = initial;
    for (int i = 0; i < N; ++i) {
        pin_to_string[current[i].first] = i;
        pin_to_string[current[i].second] = i;
    }

    struct Move { int p, s, e; };
    vector<Move> moves;

    // We process each pin i. If it's not connected to its symmetric partner j, fix it.
    for (int i = 0; i < 2 * N; ++i) {
        int j = (best_s - i + 2 * N) % (2 * N);
        if (i >= j) continue; // Only process each pair once

        int str_i = pin_to_string[i];
        int str_j = pin_to_string[j];

        if (str_i == str_j) continue; // Already parallel

        // We need pin i and pin j to be the same string.
        // Let's move the 'other' end of string i to pin j.
        int other_of_i = (current[str_i].first == i) ? current[str_i].second : current[str_i].first;
        
        // Record the move: move string str_i from 'other_of_i' to 'j'
        moves.push_back({str_i, other_of_i, j});

        // Update tracking
        // The pin 'other_of_i' is now "empty" (or rather, str_i left it)
        // String str_j no longer owns pin j
        if (current[str_i].first == i) current[str_i].second = j;
        else current[str_i].first = j;

        pin_to_string[j] = str_i;
        // Note: other_of_i is now "dangling" or will be claimed by another string later.
    }

    cout << moves.size() << "\n";
    for (auto &m : moves) {
        cout << m.p << " " << m.s << " " << m.e << "\n";
    }

    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...