【题目链接】:http://codeforces.com/problemset/problem/709/D

【题意】



给你一个序列;

给出01子列和10子列和00子列以及11子列的个数;

然后让你输出一个符合要求的序列;

【题解】



这里

00和11可以确定出序列中0和1的个数;

但有边缘数据

00如果为0代表什么?

->没有0或者是有1个0

11如果为0代表什么?

->没有1或者是有1个1

对这两种情况需要特判一下(两种情况的特判需要用到01和10的数量)

看代码吧。

然后这两种情况排除之后;

00和11就都大于0了；

则可以根据

00=a0*(a0-1)/2

11=a1*(a1-1)/2

来求出0的个数和1的个数;

具体的；

你需要对2*00开根号->x

同时你还有算一下

（x+1)*x/2是不是等于00

因为如果不是的话就表示没有符合要求的0的个数的序列满足要求;

那种情况也要输出无解;

1同理；

然后我们算出1的个数和0的个数;

把所有的1都放在最前面,然后0的放在后面;

这样a10等于0的个数乘1的个数;

然后可以验证你每把最右边那个1往右交换一个0,a10会减1,a01会加1;

则按照这个规则；

每次看看a10和输入的a10的差为多少rest

while(rest>=num0){

**把最右边那个1和最右边那个0交换;

**rest-num;

}

然后rest可能还有剩余

则把最右边那个1和这个1往右数rest个0交换位置;

就能再减去rest个10了；

根据上述规则可知；

如果输入的a10+a01!=1的个数*0的个数

则输出无解;



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define ps push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%lld",&x)

#define ref(x) scanf("%lf",&x)

typedef pair<int, int> pii;

typedef pair<LL, LL> pll;

const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };

const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };

const double pi = acos(-1.0);

const int N = 110;

int a00, a01, a10, a11;

string s;

void work(int num0, int num1){

    s = " ";

    rep1(i, 1, num1) s += '1';

    rep1(i, 1, num0) s += '0';

    if (a01 + a10 != num0*num1) puts("Impossible"),exit(0);

    int ta10 = num1*num0;

    int j = num1,i = 0;

    LL rest = ta10 - a10;

    while (rest>=num0)

    {

        swap(s[j], s[num1 + num0 - i]);

        j--; i++;

        rest -= num0;

    }

    swap(s[j], s[j + rest]);

    s.erase(0, 1);

    cout << s << endl;

    exit(0);

}

int main()

{

    //freopen("F:\\rush.txt", "r", stdin);

    rei(a00), rei(a01), rei(a10), rei(a11);

    if (a00 == 0){

        //no zero

        if (a01 == 0 && a10 == 0){

            int len = sqrt(2 * a11)+1;

            if (len*(len - 1) == 2 * a11)

            {

                rep1(i, 1, len) printf("1");

                return 0;

            }

        }

        //one zero

        if (a11 == 0){

            //no one

            if (a10 == 0 && a01 == 0) return puts("0"), 0;

            //one one

            if (a10 + a01 == 1){

                if (a10 == 1) return puts("10"), 0;

                if (a01 == 1) return puts("01"), 0;

            }

        }

        else

            if (a11 > 0) {

                int len = sqrt(2 * a11) + 1;

                if (len*(len-1)==2*a11)

                    work(1, int(sqrt(2 * a11) + 1));

            }

        puts("Impossible");

        return 0;

    }

    if (a11 == 0)

    {

        //no one

        if (a10 ==0 && a01 == 0) {

            int len = sqrt(2 * a00) + 1;

            if (len*(len - 1) == 2 * a00) {

                rep1(i, 1, len) printf("0");

                return 0;

            }

        }

        //one one

        assert(a00 > 0);

        int len = sqrt(2 * a00) + 1;

        if (len*(len - 1) == 2 * a00)

            work(int(sqrt(2 * a00) + 1), 1);

        puts("Impossible");

        return 0;

    }

    int len = sqrt(2 * a00) + 1, len1 = sqrt(2 * a11) + 1;

    if (len*(len-1)==2*a00 && len1*(len1-1)==2*a11)

        work(int(sqrt(2 * a00) + 1), int(sqrt(2 * a11) + 1));

    puts("Impossible");

    //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);

    return 0;

}