1

I was solving the CSES problem Permutations. In the questions, the user is asked to input the internet n of constraints 1≤n≤10^6 and should construct a beautiful permutation if such a permutation exists. A permutation of integers 1,2,…,n is called beautiful if there are no adjacent elements whose difference is 1.

Input

The only input line contains an integer n.

Output

Print a beautiful permutation of integers 1,2,…,n. If there are several solutions, you may print any of them. If there are no solutions, print "NO SOLUTION".

Constraints 1≤n≤10^6

Example 1

Input:
5
Output:
4 2 5 3 1

Example 2

Input:
3
Output:
NO SOLUTION

I could pass all the test cases except the last one which says "TIME EXCEED LIMIT " for the input 1000000.

Here is the code for my algorithm:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long int n;
    cin>>n;
    if(n>3 || n<2)
    {
       for(long long int i=2;i<=n;i+=2)
           cout<<i<<endl;
       for(long long int j=1;j<=n;j+=2)
           cout<<j<<endl;
    }
    else{
        cout <<"NO SOLUTION";
    }
    return 0;
     }
user3386109
  • 34,287
  • 7
  • 49
  • 68
Rabin Ghimire
  • 11
  • 2
  • 1
    For various reasons `cout` can be a little slow. Apparently in this case, too slow for this particular online judge. Using c `printf` for a strictly timed automatically judged program with a lot of output can help (and in this case does). Not recommended in general, but will help for these peculiar situations. – moreON Apr 21 '21 at 02:54
  • 1
    Another alternative is to use spaces instead of new lines (`cout< – moreON Apr 21 '21 at 02:56
  • [Another common optimization for online judges](https://stackoverflow.com/questions/31162367/significance-of-ios-basesync-with-stdiofalse-cin-tienull) – user3386109 Apr 21 '21 at 04:05
  • 1
    Using `long long int` is unnecessary and will reduce performance. `long long int` is 64-bits (or more). `long int` is 32-bits (or more). And unless the online judge is running on hardware from the 1980s, an `int` will be 32-bits (or more). The value 1000000 easily fits into 32-bits, and you aren't doing any calculations that require more bits. So I'd just use `int` variables. – user3386109 Apr 21 '21 at 04:11
  • The algorithm is fine, your C++ implementation is slow. Using cout, endl etc are not recommended for fast input-outout – Abhinav Mathur Apr 21 '21 at 04:28
  • 1
    The main problem is `endl`, it is slow to use it 1000000 times. The example shows space-delimited numbers, perhaps consider outputting the space character instead. – n. m. could be an AI Apr 21 '21 at 06:12

1 Answers1

1

Approach => for n = 2 there will be two number 1,2 and there is no way to arrange based on the constraint. (neighbor difference should be greater than 1)
same is the case for n = 3, you cannot arrange the numbers 1, 2, 3 in any order to meet the constraint. but for n = 4 there is a sequence, 2 4 1 3.
if you look at the sequence, and separate even number and then print odd number, you will get one sequence which will meet the criteria

#include <iostream>
using namespace std;

int main() {
    long n;
    cin >> n;
    if ( n == 1 ) cout << 1 << endl;
    if ( n == 2 || n == 3 ) cout << "NO SOLUTION" << endl;
    if ( n >= 4 ) {
        for( long i=2; i<=n; i+=2) printf ("%d ", i);
        for( long i=1; i<=n; i+=2) printf ("%d ", i);
    }
    return 0;
}
Cereal_Killer
  • 304
  • 2
  • 13
  • 3
    While this code may solve the question, [including an explanation](//meta.stackexchange.com/q/114762) of how and why this solves the problem would really help to improve the quality of your post, and probably result in more up-votes. Remember that you are answering the question for readers in the future, not just the person asking now. Please [edit] your answer to add explanations and give an indication of what limitations and assumptions apply. – Yunnosch Apr 21 '21 at 07:35