Submission #1364588

#TimeUsernameProblemLanguageResultExecution timeMemory
1364588shahaprogA String Problem (EGOI25_stringproblem)C++20
15 / 100
24 ms9752 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct String {
    int id, a, b;
};

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

    int N;
    cin >> N;

    vector<String> strings(N);
    vector<int> count(2 * N, 0);

    for (int i = 0; i < N; ++i) {
        strings[i].id = i;
        cin >> strings[i].a >> strings[i].b;
        // A string is "perfect" if (a + b) % 2N == S
        int s = (strings[i].a + strings[i].b) % (2 * N);
        count[s]++;
    }

    // Find the symmetry S that requires the fewest moves
    int best_s = 0;
    for (int s = 0; s < 2 * N; ++s) {
        if (count[s] > count[best_s]) {
            best_s = s;
        }
    }

    vector<vector<int>> moves;
    for (int i = 0; i < N; ++i) {
        int u = strings[i].a;
        int v = strings[i].b;
        int target_v = (best_s - u + 2 * N) % (2 * N);

        if (v == target_v) continue;

        // If the other end (v) is actually the reflection of a different target pin
        // we can check if moving 'u' instead of 'v' is better, but since the
        // goal is just ANY minimal K, fixing one end to its target always works.
        
        // Step 1: Move end 'b' to the target of 'a'
        moves.push_back({strings[i].id, v, target_v});
    }

    // Output K
    cout << moves.size() << "\n";
    for (const auto& m : moves) {
        cout << m[0] << " " << m[1] << " " << m[2] << "\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...