Submission #239638

#	Time	Username	Problem	Language	Result	Execution time	Memory
239638		Dremix10	Xylophone (JOI18_xylophone)	C++17	100 / 100	145 ms	98624 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define F first
#define S second
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define maxp 22
#define EPS (ld)(1e-18)
#define mod (int)(1e9+7)

int asked[5001][5001];

int ask(int l, int r){
    if(asked[l][r]!=-1)
        return asked[l][r];
    asked[l][r]=query(l,r);
    return asked[l][r];
}

void solve(int N) {
    int arr[N+1];

    int i,j;
    for(i=0;i<=N;i++)
        for(j=0;j<=N;j++)
        asked[i][j]=-1;

    int l=1,r=N;
    while(l<r){
        int mid=(l+r)/2;
        int x=ask(1,mid);
        if(x==N-1)
            r=mid-1;
        else
            l=mid+1;
    }
    int found;
    int x=ask(1,l);
    if(x==N-1)
        found=l;
    else
        found=l+1;
    //cout<<found<<endl;

    set<int> nums;
    for(i=1;i<N;i++)
        nums.insert(i);

    arr[found]=N;
    if(found>1){
        int x=ask(found-1,found);
        arr[found-1]=N-x;
        nums.erase(N-x);
    }
    if(found<N){
        int x=ask(found,found+1);
        arr[found+1]=N-x;
        nums.erase(N-x);
    }



    for(i=found-2;i>=1;i--){
        int x2=ask(i,i+1);
        //int x3=ask(i,i+2);
        int p1=arr[i+1]-x2;
        int p2=arr[i+1]+x2;

        if(nums.count(p1) && nums.count(p2)){
            int x3=ask(i,i+2);
            if(max({p1,arr[i+1],arr[i+2]})-min({p1,arr[i+1],arr[i+2]})==x3)
                arr[i]=p1;
            else
                arr[i]=p2;
        }
        else{
            if(nums.count(p1))
                arr[i]=p1;
            else
                arr[i]=p2;
        }
        nums.erase(arr[i]);
    }
    for(i=found+2;i<=N;i++){
        int x2=ask(i-1,i);
        //int x3=ask(i-2,i);
        int p1=arr[i-1]-x2;
        int p2=arr[i-1]+x2;

        if(nums.count(p1) && nums.count(p2)){
            int x3=ask(i-2,i);
            if(max({p1,arr[i-1],arr[i-2]})-min({p1,arr[i-1],arr[i-2]})==x3)
                arr[i]=p1;
            else
                arr[i]=p2;
        }
        else{
            if(nums.count(p1))
                arr[i]=p1;
            else
                arr[i]=p2;
        }

        nums.erase(arr[i]);
    }
    for(i=1;i<=N;i++)
        answer(i,arr[i]);

}

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