CSES 1. Two Sets (1092)

출처: https://cses.fi/problemset/task/1092

---

문제 설명

Your task is to divide the numbers 1,2,…,n into two sets of equal sum.

입력 양식

The only input line contains an integer n.

출력

Print "YES", if the division is possible, and "NO" otherwise.

After this, if the division is possible, print an example of how to create the sets. First, print the number of elements in the first set followed by the elements themselves in a separate line, and then, print the second set in a similar way.

입력 예

Example 1.

7

 

Example 2.

6

출력 예

Example 1.

YES
4
1 2 4 7
3
3 5 6

 

Example 2.

NO

제약조건

1 <= n  <= 1e6

---

문제 풀이

입력받은 n 이 4k 혹은 4k+3 인 경우에만 YES가 된다. ( (n+1)*n/2/2 == 0 ) n이 4k+3 형태인 경우와 4k 형태인 경우로 나누고, 4개 혹은 3개 그룹을 같도록 나누어서 출력한다.

프로그램 내용

#define MAX_N 1000000

int main()
{
    long long N;
    long long K;

    cin >> N;

    if ( (N+1)*N/2 % 2 != 0 )
        cout << "NO" << endl;

    if ( (N+1)*N/2 % 2 == 0 )
        cout << "YES" << endl;
        /// N = 4k + 3
        /// 2(k+1) ,
        /// 0, 3, 4, 7, ...
        if ( N % 4 == 3)
            K = (N+1) / 4;
            cout << 2*K -1 << endl;
            for (int i=0; i< K; i++)
                if ( i == 0)
                    cout << 4*i + 3 << " ";
                else
                    cout << 4*i << " " << 4*i + 3 << " ";
        /// 2(k+1)-1,
        /// 4k+2, 4k+1, 4(k-1)+2, 4(k-1)+1, ...
        /// 1, 2, 5, 6, ...
            cout << 2*K << endl;
            for (int i=1; i<= K; i++)
                cout << 4*(i-1)+1 << " " << 4*(i - 1) +2 << " ";

        if ( N % 4 == 0)
            K = N / 4;
            /// N = 4k
            /// 2(k+1) ,
            /// 1, 4, 5, 8, ...
            cout << 2*K << endl;
            for (int i=1; i<= K; i++)
                cout << 4*(i-1) + 1 << " " << 4*i << " ";

			/// N = 4k + 3
            /// 2(k+1) ,
            /// 2, 3, 6, 7, ...
            cout << 2*K << endl;
            for (int i=1; i<= K; i++)
                cout << 4*(i-1)+2 << " " << 4*(i - 1) +3 << " ";

 

Introductory problems ( link )