Submission #114978

#	Time	Username	Problem	Language	Result	Execution time	Memory
114978		IVIosab	Xylophone (JOI18_xylophone)	C++17	47 / 100	76 ms	760 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;

int a[5005];

void solve(int N) {
    int n=N;
    int value = query(1, N);
    map<pair<int,int>,int> mp;
    for(int i=1;i<n;i++){
        int t=query(i,i+1);
        mp[{i,i+1}]=t;
    }
    for(int i=1;i<n-1;i++){
        int t=query(i,i+2);
        if(mp[{i,i+1}]+mp[{i+1,i+2}]==t){
            mp[{i,i+2}]=1;
        }
    }
    int p1=1,p2=N;
    while(p2>=p1){
        int v=query(p1,p2);
        if(v!=value){
            p2++;
            break;
        }
        p2--;
    }
    while(p1<=p2){
        int v=query(p1,p2);
        if(v!=value){
            p1--;
            break;
        }
        p1++;
    }
    a[p1]=1;
    a[p2]=n;
    for(int i=p1-1;i>=1;i--){
        int t=mp[{i,i+1}];
        if(i==p1-1){
            a[i]=1+t;
        }
        else{
            if(mp[{i,i+2}]){
                if(a[i+1]>a[i+2]){
                    a[i]=a[i+1]+t;
                }
                else{
                    a[i]=a[i+1]-t;
                }
            }
            else{
                if(a[i+1]>a[i+2]){
                    a[i]=a[i+1]-t;
                }
                else{
                    a[i]=a[i+1]+t;
                }
            }
        }
    }
    if(p1!=p2-1){
        for(int i=p1+1;i<p2;i++){
            int t=mp[{i-1,i}];
            if(i==p1+1){
                a[i]=1+t;
            }
            else{
                if(mp[{i-2,i}]){
                    if(a[i-2]>a[i-1]){
                        a[i]=a[i-1]-t;
                    }
                    else{
                        a[i]=a[i-1]+t;
                    }
                }
                else{
                    if(a[i-2]>a[i-1]){
                        a[i]=a[i-1]+t;
                    }
                    else{
                        a[i]=a[i-1]-t;
                    }
                }
            }
        }
    }
    for(int i=p2+1;i<=n;i++){
        int t=mp[{i-1,i}];
        if(i==p2+1){
            a[i]=n-t;
        }
        else{
            if(mp[{i-2,i}]){
                if(a[i-2]>a[i-1]){
                    a[i]=a[i-1]-t;
                }
                else{
                    a[i]=a[i-1]+t;
                }
            }
            else{
                if(a[i-2]>a[i-1]){
                    a[i]=a[i-1]+t;
                }
                else{
                    a[i]=a[i-1]-t;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        answer(i,a[i]);
    }
}

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