Prefix Sums solution in C++ language.- Codechef

   

Prefix Sums

Problem Code: UNQEQ

---

For a positive, $\mathbf{\text{even}}$ integer $�$, we call a pair of arrays $�$ and $�$ to be interesting if they satisfy the following conditions :

• $\mathrm{\mid }�\mathrm{\mid }=\mathrm{\mid }�\mathrm{\mid }=�\mathrm{/}2$ i.e. the length of array $�$ is equal to the length of array $�$.

• Each integer from $1$ to $�$ occurs exactly once in exactly one of the arrays.

• The ${�}^{�ℎ}$ prefix sum of $�$ is not equal to ${�}^{�ℎ}$ prefix sum of $�$ for all $1\le �\le �\mathrm{/}2-1$. Formally, ${\displaystyle \sum _{�=1}^{�}{�}_{�}\mathrm{\ne }\sum _{�=1}^{�}{�}_{�}}$ for all $1\le �\le �\mathrm{/}2-1$

• Sum of all elements in $�$ is equal to sum of all elements in $�$ i.e. ${\displaystyle \sum _{�=1}^{�\mathrm{/}2}{�}_{�}=\sum _{�=1}^{�\mathrm{/}2}{�}_{�}}$

You are given a positive, even integer $�$. If there exists an interesting pair of arrays, then print "YES" followed by an interesting pair for this given $�$. If there exists multiple interesting pairs of arrays for given $�$, you can print any. Print "NO" in a single line if no such pair exists.

Input Format

First line of input will contain $�$, the number of test cases. Then the test cases follow.

Each test case contains a single line of input, the integer $�$.

Output Format

For each test case, if there exists an interesting pair of arrays, say $(�,�)$, then in the first line print "YES", in the second line print array $�$ separated by spaces, and in third line print array $�$ separated by spaces. Print "NO" in a single line if no such pair exists. If there are multiple answers, print any of them.

Constraints

• $1\le T\le 10^5$
• $1\le �\le 10^5$
• $�$ is guaranteed to be even.
• Sum of $�$ over all test cases doesn't exceed $10^6$
• Subtask 1 (100 points): Original constraints

Sample Input 1 

2
2
4

Sample Output 1 

NO
YES
1 4
2 3

Explanation

Test case 2: Consider $�=[1,4]$ and $�=[2,3]$. Every integer from $1$ to $4$ occurs exactly once in exactly one of the arrays. Also, $1$st prefix sum of $�$ is not equal to $1$st prefix sum of $�$ ($1\mathrm{\ne }2$). And sum of the elements is equal to $5$ for both arrays. So, $(�,�)$ is an interesting pair.

. . .
Solution in C++.

#include <bits/stdc++.h>
using namespace std;

#define pb push_back

int main() {
	// your code goes here
	
	int t;
	cin >> t;
	while(t--){
	    int n;
	    cin >> n;
	    if(n%4!=0) cout << "NO" << endl;
	    else{
	        vector<int> a;
	        vector<int> b;
	        int first=1, last=n, x=0;
	        for(int i=0;i<n/2;i++){
	            if(x==0){
	                a.pb(first);
	                first++;
	                x=1;
	            }
	            else{
	                a.pb(last);
	                last--;
	                x=0;
	            }
	        }
	        for(int i=first;i<=last;i++) b.pb(i);
	        sort(a.begin(),a.end());
	        sort(b.begin(),b.end());
            cout << "YES" << endl;
            for(auto i:a) cout<<i<<" "; 
            cout << "\n"; 
            for(auto i:b) cout<<i<<" "; 
            cout << "\n"; 
	    }
	}
	return 0;
}