Submission #763058

#	Time	Username	Problem	Language	Result	Execution time	Memory
763058		huutuan	Xylophone (JOI18_xylophone)	C++14	100 / 100	104 ms	440 KiB

xylophone

#include<bits/stdc++.h>
#include "xylophone.h"

using namespace std;

int a[5001], b[5001], ans1[5001], ans2[5001];

void sus(int N, int last, int* ans){
    if (last) ans[1]=1, ans[2]=1-a[1];
    else ans[1]=1, ans[2]=1+a[1];
    for (int i=1; i+2<=N; ++i){
        int v1=a[i], v2=a[i+1], v3=b[i];
        if (v1==v3){
            if (ans[i]<ans[i+1]) ans[i+2]=ans[i+1]-v2;
            else ans[i+2]=ans[i+1]+v2;
        }else{
            if (ans[i]<ans[i+1]){
                if (v2==v3) ans[i+2]=ans[i+1]-v2;
                else ans[i+2]=ans[i+1]+v2;
            }else{
                if (v2==v3) ans[i+2]=ans[i+1]+v2;
                else ans[i+2]=ans[i+1]-v2;
            }
        }
    }
    int m=*min_element(ans+1, ans+N+1);
    for (int i=1; i<=N; ++i) ans[i]-=m-1;
}

int pos[5001];

bool check(int N, int* ans){
    memset(pos, 0, sizeof pos);
    for (int i=1; i<=N; ++i){
        if (ans[i]<1 || ans[i]>N) return 0;
        pos[ans[i]]=i;
    }
    if (*min_element(pos+1, pos+N+1)==0) return 0;
    return pos[1]<pos[N];
}

void lmao(int N, int* ans){
    for (int i=1; i<=N; ++i) answer(i, ans[i]);
}

void solve(int N){
    for (int i=1; i<N; ++i) a[i]=query(i, i+1);
    for (int i=1; i<N-1; ++i) b[i]=query(i, i+2);
    sus(N, 0, ans1);
    sus(N, 1, ans2);
    if (check(N, ans1)) lmao(N, ans1);
    else{
        assert(check(N, ans2));
        lmao(N, ans2);
    }
}

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