Submission #256566

#	Time	Username	Problem	Language	Result	Execution time	Memory
256566		DavidDamian	Xylophone (JOI18_xylophone)	C++11	100 / 100	265 ms	636 KiB

xylophone

#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
///Subtask 3
///2N queries
///Ask for i,i+1 and i,i+2
///Determine the direction of the changes with adj3[i]==adj2[i]+adj2[i+1]
int a[5005];
int adj2[5005]; //Differences of pairs
int adj3[5005]; //Differences of triples
int same[5005];
bool found=false;
void build(int n,int k,int dir)
{
    bool one=false;
    a[1]=k;
    for(int i=1;i<=n-1;i++){
        if(a[i]==1) one=true;
        if(!same[i]) dir*=-1;
        a[i+1]=a[i]+dir*adj2[i];
        if(a[i+1]<1 || a[i+1]>n)
            return;
        if(a[i+1]==n && !one)
            return;
    }
    found=true;
}
void print(int n)
{
    for(int i=1;i<=n;i++){
        answer(i,a[i]);
    }
}
void solve(int N) {
    if(N==2){
        answer(1,1);
        answer(2,2);
        return;
    }
    for(int i=1;i<=N-2;i++){
        adj2[i]=query(i,i+1);
        adj3[i]=query(i,i+2);
    }
    adj2[N-1]=query(N-1,N);
    same[1]=1;
    for(int i=1;i<=N-2;i++){
        if(adj3[i]==adj2[i]+adj2[i+1])
            same[i+1]=1;
    }
    for(int i=1;i<=N;i++){
        build(N,i,1);
        if(found){
            print(N);
            return;
        }
        build(N,i,-1);
        if(found){
            print(N);
            return;
        }
    }
}

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