CodeForces 125D【鸽巢原理】

哇塞？开始的三个数其中两个数一定能确定一个序列。（鸽巢原理）

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=3e4+10;

int a[N],n;

bool vis[N];

void print(vector<int>v)

{

    int sz = v.size();

    for(int i=0; i<sz; i++)

        printf("%d ",v[i]);

    puts("");

}

bool check(vector<int>v)

{

    if(!v.size())

        return false;

    if(v.size()==1||v.size()==2) return true;

    int d=v[1]-v[0];

    for(int i=2; i<v.size(); i++)

        if(v[i]-v[i-1]!=d)

            return false;

    return true;

}

bool solve(int l,int r)

{

    vector<int>v1,v2;

    memset(vis,false,sizeof(vis));

    int d=a[r]-a[l];

    int last=-1,get=a[l];

    for(int i=1; i<=n; i++)

        if(a[i]==get)

        {

            get+=d;

            v1.push_back(a[i]);

            last=i;

        }

        else vis[i]=1;

    for(int i=1; i<=n; i++)

        if(vis[i])

            v2.push_back(a[i]);

    if(check(v2))

    {

        print(v1);

        print(v2);

        return true;

    }

    vis[last]=1;

    v1.pop_back();

    v2.clear();

    for(int i=1; i<=n; i++)

        if(vis[i])

            v2.push_back(a[i]);

    if(check(v2))

    {

        print(v1);

        print(v2);

        return true;

    }

    return false;

}

int main()

{

    scanf("%d",&n);

    for(int i=1; i<=n; i++)

        scanf("%d",&a[i]);

    if(n==2)

        printf("%d\n%d",a[1],a[2]);

    else if(!solve(1,2)&&!solve(2,3)&&!solve(1,3))

        printf("No solution");

    return 0;

}