Marin and Anti-coprime Permutation codeforces solution in c++

#include <iostream>
#include <vector>

using namespace std;

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

    if (n == 1) {
        cout << "1\n";
        return 0;
    }

    if (n <= 3) {
        cout << "NO SOLUTION\n";
        return 0;
    }

    vector<int> permutation;
    for (int i = 2; i <= n; i += 2) {
        permutation.push_back(i);
    }
    for (int i = 1; i <= n; i += 2) {
        permutation.push_back(i);
    }

    for (int i = 0; i < n; i++) {
        cout << permutation[i] << " ";
    }
    cout << "\n";

    return 0;
}

Explanation:

1. Include Libraries: The code starts by including the necessary libraries - iostream for input/output operations and vector to use a dynamic array.

2. Main Function: The program's execution starts from the main() function.

3. Input: It reads an integer n from the standard input (keyboard).

4. Special Cases Handling:

   • If n is 1, the program outputs "1" and terminates.
   • If n is less than or equal to 3, there is no solution, so it outputs "NO SOLUTION" and terminates.

5. Permutation Generation:

   • For n greater than 3, it initializes an empty vector permutation to store the permutation.
   • Two loops are used:
     • The first loop (for (int i = 2; i <= n; i += 2)) adds even numbers starting from 2 to n to the permutation vector.
     • The second loop (for (int i = 1; i <= n; i += 2)) adds odd numbers starting from 1 to n to the permutation vector.

6. Output:

   • Finally, it prints the generated permutation stored in the permutation vector.

This code generates a permutation of numbers from 1 to n such that for any number x in the permutation, x and x+1 are not coprime (do not have a greatest common divisor of 1).