Submission #434032

#	Time	Username	Problem	Language	Result	Execution time	Memory
434032		LouayFarah	Xylophone (JOI18_xylophone)	C++14	100 / 100	231 ms	196420 KiB

xylophone

#include "bits/stdc++.h"
#include "xylophone.h"
using namespace std;

#define ll long long 
#define pb push_back

void solve(int n)
{
    /*o.resize(n+1);
    for(int i = 1; i<=n; i++)
        cin >> o[i];*/

    vector<vector<ll>> q(n+1, vector<ll>(n+1));
    for(int i = 1; i<n; i++)
        q[i][i+1] = query(i, i+1);
    for(int i = 1; i<n-1; i++)
        q[i][i+2] =query(i, i+2);

    bool flag = true;
    vector<ll> arr(n+1);
    arr[1] = 0;
    for(int i = 1; i<n; i++)
    {
        if(q[i][i+2]==q[i][i+1] + q[i+1][i+2])
        {
            if(flag)
                arr[i+1] = arr[i] + q[i][i+1];
            else
                arr[i+1] = arr[i] - q[i][i+1];
        }
        else
        {
            if(flag)
                arr[i+1] = arr[i] + q[i][i+1];
            else
                arr[i+1] = arr[i] - q[i][i+1];
            flag = !flag;
        }
    }

    ll mini = 1e9;
    for(int i = 1; i<=n; i++)
        mini = min(mini, arr[i]);
    ll dif = 1-mini;

    for(int i = 1; i<=n; i++)
        arr[i]+=dif;

    int l = 1, r = n;
    for(int i = 1; i<=n; i++)
    {
        if(arr[i]==1)
            l = i;
        if(arr[i]==n)
            r = i;
    }

    if(l>=r)
    {
        flag = false;
        arr.assign(n+1, 0);
        arr[1] = 0;
        for(int i = 1; i<n; i++)
        {
            if(q[i][i+2]==q[i][i+1] + q[i+1][i+2])
            {
                if(flag)
                    arr[i+1] = arr[i] + q[i][i+1];
                else
                    arr[i+1] = arr[i] - q[i][i+1];
            }
            else
            {
                if(flag)
                    arr[i+1] = arr[i] + q[i][i+1];
                else
                    arr[i+1] = arr[i] - q[i][i+1];
                flag = !flag;
            }
        }

        ll mini = 1e9;
        ll dif = 0;
        for(int i = 1; i<=n; i++)
            mini = min(mini, arr[i]);
        dif = 1 - mini;
        for(int i = 1; i<=n; i++)
            arr[i]+=dif;

        for(int i = 1; i<=n; i++)
            answer(i, arr[i]);
        return;
    }

    for(int i = 1; i<=n; i++)
        answer(i, arr[i]);
    return;
}

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