Submission #256343

#	Time	Username	Problem	Language	Result	Execution time	Memory
256343		DavidDamian	Xylophone (JOI18_xylophone)	C++11	47 / 100	115 ms	620 KiB

xylophone

#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
///Subtask 2
///Same idea of subtask 1 implementing binary search (N log N queries)
int memo[105][105];
int a[105];
int binarySearch(int type,int s,int t,int value)
{
    int L=s;
    int R=t;
    if(type<=2){
        int j=t-1;
        while(L<=R){
            int mid=(L+R)/2;
            if(query(s,mid)!=value){
                j=mid;
                L=mid+1;
            }
            else
                R=mid-1;
        }
        return j;
    }
    else{
        int j=s+1;
        while(L<=R){
            int mid=(L+R)/2;
            if(query(mid,t)!=value){
                j=mid;
                R=mid-1;
            }
            else
                L=mid+1;
        }
        return j;
    }
}
void goodRange(int type,int s,int t)
{
    if(s==t) return;
    if(type<=2){
        if(a[t]!=0) t--;
        if(s==t) return;
        int value=query(s,t);
        int j=binarySearch(type,s,t,value);
        a[j+1]=(type==1)? a[s]+value : a[s]-value;
        int nextType=(type==1)? 2 : 1;
        goodRange(nextType,j+1,t);
        goodRange(nextType+2,s,j+1);
    }
    else{
        if(a[s]!=0) s++;
        if(s==t) return;
        int value=query(s,t);
        int j=binarySearch(type,s,t,value);
        a[j-1]=(type==3)? a[t]+value : a[t]-value;
        int nextType=(type==3)? 4 : 3;
        goodRange(nextType,s,j-1);
        goodRange(nextType-2,j-1,t);
    }
}
void solve(int N) {
    int j=binarySearch(1,1,N,N-1);
    a[j+1]=N;
    goodRange(4,1,j+1);
    goodRange(2,j+1,N);
    for(int i=1;i<=N;i++){
        answer(i,a[i]);
    }
}

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