Submission #477516

#	Time	Username	Problem	Language	Result	Execution time	Memory
477516		nicolaalexandra	Xylophone (JOI18_xylophone)	C++14	100 / 100	60 ms	544 KiB

xylophone

#include <bits/stdc++.h>
#include "xylophone.h"
#define DIM 5010
using namespace std;

int v[DIM],a[DIM],f[DIM];
int n,i,pas;
/*
void answer (int i, int val){
    //cout<<i<<" "<<val<<"\n";
    cout<<val<<"\n";
}

int query (int x, int y){
    pas++;
    int maxi = 0, mini = n+1;
    for (int i=x;i<=y;i++){
        mini = min (mini,a[i]);
        maxi = max (maxi,a[i]);
    }
    return maxi - mini;
}
*/

void solve (int n){

    /// determin pozitia lui n
    int st = 1, dr = n, sol_poz;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (query(1,mid) == n-1){
            sol_poz = mid;
            dr = mid-1;
        } else st = mid+1;
    }

    v[sol_poz] = n;

    /*divide (1,sol_poz-1,n,1,1);
    divide (sol_poz+1,n,n,1,0);
    */

    f[n] = 1;

    if (sol_poz > 1){
        v[sol_poz-1] = n - query (sol_poz-1,sol_poz);
        f[v[sol_poz-1]] = 1;
    }

    if (sol_poz < n){
        v[sol_poz+1] = n - query (sol_poz,sol_poz+1);
        f[v[sol_poz+1]] = 1;
    }

    for (i=sol_poz-2;i>=1;i--){
        int dif = query (i,i+1);

        if (v[i+1] - dif <= 0){
            v[i] = v[i+1] + dif;
            f[v[i]] = 1;
            continue;
        }

        if (v[i+1] + dif > n){
            v[i] = v[i+1] - dif;
            f[v[i]] = 1;
            continue;
        }

        if (!f[v[i+1]-dif] && !f[v[i+1]+dif]){ /// am doua variante posibile

            int dif2 = query (i,i+2);

            int val = v[i+1] + dif;
            if (max(val,max(v[i+1],v[i+2])) - min (val,min(v[i+1],v[i+2])) == dif2)
                v[i] = val;
            else v[i] = v[i+1] - dif;

            /*
            if (dif2 == max(v[i+1],v[i+2]) - min(v[i+1],v[i+2])){

                if (v[i+1] < v[i+2])
                    v[i] = v[i+1] + dif;
                else v[i] = v[i-1] - dif;

            } else {

                if (dif2 == dif){

                    if (v[i+1] < v[i+2])
                        v[i] = v[i+1] + dif;
                    else v[i] = v[i+1] - dif;

                } else {

                    if (v[i+1] < v[i+2])
                        v[i] = v[i+1] - dif;
                    else v[i] = v[i+1] + dif;

                }

            }
            */

            f[v[i]] = 1;

            continue;
        }


        if (!f[v[i+1]-dif]){
            v[i] =  v[i+1] - dif;
            f[v[i]] = 1;
        } else {
            v[i] = v[i+1] + dif;
            f[v[i]] = 1;
        }
    }

    for (i=sol_poz+2;i<=n;i++){

        int dif = query (i-1,i);
        if (v[i-1] - dif <= 0){
            v[i] = v[i-1] + dif;
            f[v[i]] = 1;
            continue;
        }

        if (v[i-1] + dif > n){
            v[i] = v[i-1] - dif;
            f[v[i]] = 1;
            continue;
        }

        if (!f[v[i-1]-dif] && !f[v[i-1]+dif]){

            int dif2 = query (i-2,i);
            if (max(v[i-1]+dif,max(v[i-1],v[i-2])) - min(v[i-1]+dif,min(v[i-1],v[i-2])) == dif2)
                v[i] = v[i-1] + dif;
            else v[i] = v[i-1] - dif;

            f[v[i]] = 1;

            continue;
        }

        if (!f[v[i-1]-dif]){
            v[i] = v[i-1] - dif;
            f[v[i]] = 1;
        } else {
            v[i] = v[i-1] + dif;
            f[v[i]] = 1;
        }


    }


    for (int i=1;i<=n;i++)
        answer (i,v[i]);

}

/*
int main (){


    ifstream cin ("date.in");
    ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<=n;i++)
        cin>>a[i];

    solve (n);

    cout<<pas;

    return 0;
}
*/

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:51:34: warning: 'sol_poz' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |         v[sol_poz+1] = n - query (sol_poz,sol_poz+1);
      |                            ~~~~~~^~~~~~~~~~~~~~~~~~~

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