제출 #1188844

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188844		alexdd	Xylophone (JOI18_xylophone)	C++20	100 / 100	26 ms	460 KiB

xylophone

#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
static int q2[5005],q3[5005];
static int a[5005];
bool calc(int a2, int N)
{
    a[1] = 0;
    a[2] = a2;
    for(int i=3;i<=N;i++)
    {
        bool isbigger;
        if(a[i-2] > a[i-1])
        {
            if(q3[i] == q2[i] + q2[i-1])//a
                isbigger=0;
            else
                isbigger=1;
        }
        else
        {
            if(q3[i] == q2[i] + q2[i-1])
                isbigger=1;
            else
                isbigger=0;
        }

        if(isbigger)
            a[i] = a[i-1] + q2[i];
        else
            a[i] = a[i-1] - q2[i];
    }
    int mnm = N;
    for(int i=1;i<=N;i++)
        mnm = min(mnm, a[i]);
    for(int i=1;i<=N;i++)
        a[i] += -mnm + 1;

    int poz1=-1,pozN=-1;
    for(int i=1;i<=N;i++)
    {
        if(a[i]==1)
            poz1=i;
        if(a[i]==N)
            pozN=i;
    }
    return poz1 < pozN;
}
void solve(int N)
{
    for(int i=2;i<=N;i++)
        q2[i] = query(i-1,i);
    for(int i=3;i<=N;i++)
        q3[i] = query(i-2,i);

    if(calc(q2[2],N))
    {
        for(int i=1;i<=N;i++)
            answer(i, a[i]);
    }
    else if(calc(-q2[2],N))
    {
        for(int i=1;i<=N;i++)
            answer(i, a[i]);
    }
    else
    {
        assert(0);
    }
}
/*

5
2 1 5 3 4

*/

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