Submission #739460

#	Time	Username	Problem	Language	Result	Execution time	Memory
739460		Valters07	Xylophone (JOI18_xylophone)	C++14	100 / 100	173 ms	556 KiB

xylophone

#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
const int N = 5005;

int a[N];
int nxt2[N], nxt3[N];

void solve(int n)
{
    for(int i = 1;i<n;i++)
        nxt2[i]=query(i,i+1);
    for(int i = 1;i<n-1;i++)
        nxt3[i]=query(i,i+2);
    a[1]=nxt2[1];
    for(int i = 3;i<=n;i++)
    {
        bool t1 = (nxt2[i-2]+nxt2[i-1]==nxt3[i-2]);
        bool t2 = (a[i-2]<a[i-1]);
        if(t1^t2)
            a[i]=a[i-1]-nxt2[i-1];
        else
            a[i]=a[i-1]+nxt2[i-1];
    }
    int mipos = 1, mapos = 1;
    for(int i = 1;i<=n;i++)
    {
        if(a[mipos]>a[i])
            mipos=i;
        if(a[mapos]<a[i])
            mapos=i;
    }
    if(mipos>mapos)
    {
        swap(mipos,mapos);
        for(int i = 1;i<=n;i++)
            a[i]=-a[i];
    }
    int pl = -a[mipos]+1;
    for(int i = 1;i<=n;i++)
        a[i]+=pl;
    for(int i = 1;i<=n;i++)
        answer(i,a[i]);
}

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