【Codeforces Round #452 (Div. 2) C】 Dividing the numbers

在这里输入题意

【题解】

1.
n为偶数。
l = 1, r = n
(l,r)放在一组
l++,r--
新的l,r放在另外一组
直到l+1==r
这个时候,判断两组的和,如果一样的话,分散在两组
差为1否则差为0
2.
n为奇数
l = 2,r = n
(l,r)放在一组
l++,r--
新的l,r放在另外一组
直到l+1==r
这个时候,判断两组的和,如果一样的话,分散在两组
差为0(把1放在那个较少的组)
否则,差为1
1随意放在哪一组都可以

【代码】

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int n;

int now = 0;

vector<ll> v[2];

ll sum[2];

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

    cin >> n;

    if (n%2==0){

        int l = 1,r = n;

        while (l+1<r){

            v[now].push_back(l);

            v[now].push_back(r);

            sum[now]+=(l+r);

            now = now^1;

            l++,r--;

        }

        ll differ = 0;

        if (sum[0]!=sum[1]){

            v[now].push_back(l);

            v[now].push_back(r);

            differ = 0;

        }else{

            differ = 1;

            v[0].push_back(l);

            v[1].push_back(r);

        }

        cout << differ<<endl;

        cout << (int) v[0].size();

        for (int i = 0;i < (int) v[0].size();i++) cout <<' '<< v[0][i];

    }else{

        int l = 2,r = n;

        while (l+1<r){

            v[now].push_back(l);

            v[now].push_back(r);

            sum[now]+=(l+r);

            now = now^1;

            l++,r--;

        }

        ll differ = 0;

        if (sum[0]!=sum[1]){

            v[now].push_back(l);

            v[now].push_back(r);

            differ = 1;

        }else{

            differ = 0;

            v[0].push_back(l);

            v[0].push_back(1);

            v[1].push_back(r);

        }

        cout << differ<<endl;

        cout << (int) v[0].size();

        for (int i = 0;i < (int) v[0].size();i++) cout <<' '<< v[0][i];

    }

	return 0;

}

巴特西

【Codeforces Round #452 (Div. 2) C】 Dividing the numbers

最新文章

热门文章