Submission #256275

#	Time	Username	Problem	Language	Result	Execution time	Memory
256275		DavidDamian	Xylophone (JOI18_xylophone)	C++11	11 / 100	64 ms	504 KiB

xylophone

#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
///Subtask 1
///Use N^2 queries and fix ranges with minimum or maximum in one of its ends
int memo[105][105];
int a[105];
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 j=t;
        int value=memo[s][t];
        while(memo[s][j]==value) j--;
        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=memo[s][t];
        int j=s;
        while(memo[j][t]==value) j++;
        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) {
    if(N>100) return;
    for(int i=1;i<=N;i++){
        for(int j=i+1;j<=N;j++){
            memo[i][j]=query(i,j);
        }
    }
    int j=N;
    while(memo[1][j]==N-1) j--;
    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: 0 / 36
• Subtask 3: 0 / 53