Submission #996196

#	Time	Username	Problem	Language	Result	Execution time	Memory
996196		vjudge1	Xylophone (JOI18_xylophone)	C++14	100 / 100	67 ms	592 KiB

xylophone

#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
/*void answer(int a,int b){
    cout << b << ' ';
}
const int MAXN=5000;
int p[MAXN+1];
int query(int s,int e){
    int Min=p[s],Max=p[s];
    for(int i=s;i<=e;i++){

        Min=min(Min,p[i]);
        Max=max(Max,p[i]);
    }
    return (Max-Min);
}*/
void solve(int n){
	if(n==1){
       answer(1,1);
    }
    else if(n==2){
        answer(1,1);
        answer(2,2);
    }
    else{
        int diff2[n+1];
        int diff1[n+1];
        for(int i=3;i<=n;i++){
            diff1[i]=query(i-1,i);
            diff2[i]=query(i-2,i);
        }
        int a[n+1];
        int dist=query(1,2);
        bool inva=true;
        for(int m=-1;m<=1;m+=2){
            a[1]=10000;
            a[2]=a[1]+m*dist;
            int Min=min(a[1],a[2]);
            for(int i=3;i<=n;i++){
                if(diff2[i]==diff1[i]+abs(a[i-2]-a[i-1])){
                    if(a[i-2]>a[i-1]){
                        a[i]=a[i-1]-diff1[i];
                    }
                    else{
                        a[i]=a[i-1]+diff1[i];
                    }
                }
                else if(diff2[i]==max(diff1[i],abs(a[i-2]-a[i-1]))){
                    if(a[i-2]>a[i-1]){
                        a[i]=a[i-1]+diff1[i];
                    }
                    else{
                        a[i]=a[i-1]-diff1[i];
                    }
                }
                else{
                    inva=false;
                    break;
                }
                Min=min(Min,a[i]);
            }
            if(!inva){
                continue;
            }
            Min--;
            bool mark[n+1]={false};
            bool flag=true;
            for(int i=1;i<=n;i++){
                a[i]-=Min;
                if(a[i]>n||a[i]<1||mark[a[i]]){
                    flag=false;
                    break;
                }
                if(a[i]==n&&!mark[1]){
                    flag=false;
                    break;
                }
                mark[a[i]]=true;
            }
            if(flag){
                for(int i=1;i<=n;i++){
                    answer(i,a[i]);
                }
                break;
            }
        }
    }
}

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