CodeForces 125D [비둘기 둥지 원리]

1507 단어 codeforces
와싸시작된 세 개의 수 중 두 개의 수는 반드시 하나의 서열을 확정할 수 있다.(비둘기 둥지 원리)
#include 
using namespace std;
typedef long long LL;

const int N=3e4+10;

int a[N],n;
bool vis[N];

void print(vectorv)
{
    int sz = v.size();
    for(int i=0; iv)
{
    if(!v.size())
        return false;
    if(v.size()==1||v.size()==2) return true;

    int d=v[1]-v[0];
    for(int i=2; iv1,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
%d",a[1],a[2]); else if(!solve(1,2)&&!solve(2,3)&&!solve(1,3)) printf("No solution"); return 0; }

좋은 웹페이지 즐겨찾기