Submission #989236

#	Time	Username	Problem	Language	Result	Execution time	Memory
989236		user736482	Xylophone (JOI18_xylophone)	C++17	100 / 100	72 ms	600 KiB

xylophone

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

/*void answer(int a,int b){
    cout<<b<<" k ";
}
int query(int a,int b){
    vector<int>v={2,1,5,3,4};
    int min_=99999,max_=0;
    for(int i=a-1;i<b;i++){
        min_=min(min_,v[i]);
        max_=max(max_,v[i]);
    }
    return max_-min_;
}*/
void solve(int n){
    int tab1[n],tab2[n],ak,ak2,ak3;
    tab1[0]=0,tab2[0]=0;
    if(n==1){
        answer(1,1);
        return;
    }
    if(n==2){
        answer(1,1);
        answer(2,2);
        return;
    }
    ak2=query(1,2);
    tab1[1]=ak2;
    tab2[1]=-ak2;
    //cout<<tab1[0]<<" "<<tab2[0]<<"\n";
    //cout<<tab1[1]<<" "<<tab2[1]<<"\n";
    for(int i=2;i<n;i++){
        ak3=ak2;
        ak=query(i-1,i+1);
        ak2=query(i,i+1);
        if(tab1[i-1]>tab1[i-2]){
            tab1[i]=tab1[i-1]+ak2*((ak-ak3==ak2)*2-1);
        }
        else{
            tab1[i]=tab1[i-1]-ak2*((ak-ak3==ak2)*2-1);
        }
        if(tab2[i-1]>tab2[i-2]){
            //cout<<tab2[i-2]<<" "<<tab2[i-1]<<"   ";
            tab2[i]=tab2[i-1]+ak2*((ak-ak3==ak2)*2-1);
        }
        else{
            tab2[i]=tab2[i-1]-ak2*((ak-ak3==ak2)*2-1);
        }
        //cout<<tab1[i]<<" "<<tab2[i]<<"\n";
    }
    ak=99999;
    for(int i=0;i<n;i++){
        ak=min(ak,tab1[i]);
    }
    for(int i=0;i<n;i++){
        tab1[i]-=(ak-1);
    }
    for(int i=0;i<n;i++){
        if(tab1[i]==1){
            for(int j=0;j<n;j++){
                answer(j+1,tab1[j]);
            }
            return;
        }
        if(tab1[i]==n)
            break;
    }
    ak=99999;
    for(int i=0;i<n;i++){
        ak=min(ak,tab2[i]);
    }
    for(int i=0;i<n;i++){
        tab2[i]-=(ak-1);
    }
    for(int j=0;j<n;j++){
        answer(j+1,tab2[j]);
    }
}
//int main(){
//    solve(5);
//}

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