Submission #467969

#	Time	Username	Problem	Language	Result	Execution time	Memory
467969		stefantaga	Xylophone (JOI18_xylophone)	C++14	100 / 100	263 ms	580 KiB

xylophone

#include <cstdio>
#include <cstdlib>
#include "xylophone.h"
#include <bits/stdc++.h>
int doi[10005],trei[10005],v[10005],fr[10005],ok,val1;
int max1(int a,int b)
{
    if (a>b)
    {
        return a;
    }
    return b;
}
int min1(int a,int b)
{
    if (a<b)
    {
        return a;
    }
    return b;
}
int valoare(int a,int b,int c)
{
    int maxim=max1(a,max1(b,c));
    int minim=min1(a,min1(b,c));
    return maxim-minim;
}
void solve(int n) {
    int i,j;
    for (i=1;i<=n-1;i++)
    {
        doi[i]=query(i,i+1);
    }
    for (i=1;i<=n-2;i++)
    {
        trei[i]=query(i,i+2);
    }
    for (i=2;i<=n;i++)
    {
        /// presupun ca pe pozitia i am N
        for (j=1;j<=n;j++)
        {
            v[j]=0;
            fr[j]=0;
        }
        v[i]=n;
        v[i-1]=n-doi[i-1];
        ok=1;
        for (j=i-2;j>=1;j--)
        {
            if (v[j+1]-doi[j]>=1)
            {
                val1=v[j+1]-doi[j];
                if (valoare(val1,v[j+1],v[j+2])==trei[j])
                {
                    v[j]=val1;
                    continue;
                }
            }
            if (v[j+1]+doi[j]<=n)
            {
                val1=v[j+1]+doi[j];
                if (valoare(val1,v[j+1],v[j+2])==trei[j])
                {
                    v[j]=val1;
                    continue;
                }
            }
            ok=0;
            break;
        }
        if (ok==0)
        {
            continue;
        }
        if (i<n)
        {
            v[i+1]=n-doi[i];
            for (j=i+2;j<=n;j++)
            {
                if (v[j-1]-doi[j-1]>=1)
                {
                    val1=v[j-1]-doi[j-1];
                    if (valoare(val1,v[j-1],v[j-2])==trei[j-2])
                    {
                        v[j]=val1;
                        continue;
                    }
                }
                if (v[j-1]+doi[j-1]<=n)
                {
                    val1=v[j-1]+doi[j-1];
                    if (valoare(val1,v[j-1],v[j-2])==trei[j-2])
                    {
                        v[j]=val1;
                        continue;
                    }
                }
                ok=0;
                break;
            }
        }
        if (ok==0)
            {
                continue;
            }
            int poz=n+1;
            for (j=1;j<=n;j++)
            {
                if (v[j]==1)
                {
                    poz=j;
                }
                if (fr[v[j]]!=0)
                {
                    ok=0;
                    break;
                }
                fr[v[j]]=1;
            }
            if (ok==0)
            {
                continue;
            }
            if (poz>i)
            {
                continue;
            }
            for (j=1;j<=n;j++)
            {
                answer(j,v[j]);
            }
            break;
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 53 / 53