Submission #558102

#	Time	Username	Problem	Language	Result	Execution time	Memory
558102		groshi	Xylophone (JOI18_xylophone)	C++17	100 / 100	70 ms	428 KiB

xylophone

#include<iostream>
#include "xylophone.h"
using namespace std;
bool bylo[100000];
int jaki[100000];
/*int query(int x,int y)
{
    cout<<x<<" "<<y<<"\n";
    int co;
    cin>>co;
    return co;
}
int answer(int x,int y)
{
    cout<<y<<" ";
}*/
void solve(int n)
{
    int pocz=1,kon=n+1,sre,ostd=n-1;
    while(pocz<kon)
    {
        sre=(pocz+kon)/2;
        int k=query(sre,n);
        if(k==n-1)
        {
            ostd=sre;
            pocz=sre+1;
        }
        else{
            kon=sre;
        }
    }
    jaki[ostd]=1;
    bylo[1]=1;
    for(int i=ostd+1;i<=n;i++)
    {
        int k=query(i-1,i);
        if(jaki[i-1]-k<=0 || bylo[jaki[i-1]-k]==1)
            jaki[i]=jaki[i-1]+k;
        else if(jaki[i-1]+k>n || bylo[jaki[i-1]+k]==1)
            jaki[i]=jaki[i-1]-k;
        else{
            int k1=query(i-2,i);
            if(jaki[i-2]<jaki[i-1])
            {
                int odl=jaki[i-1]-jaki[i-2];
                if(k1==odl+k)
                    jaki[i]=jaki[i-1]+k;
                else jaki[i]=jaki[i-1]-k;
            }
            else{
                int odl=jaki[i-2]-jaki[i-1];
                if(k1==k+odl)
                    jaki[i]=jaki[i-1]-k;
                else jaki[i]=jaki[i-1]+k;
            }
        }
        bylo[jaki[i]]=1;
    }
    for(int i=ostd-1;i>=1;i--)
    {
        int k=query(i,i+1);
        if(jaki[i+1]-k<=0 || bylo[jaki[i+1]-k]==1)
            jaki[i]=jaki[i+1]+k;
        else if(jaki[i+1]+k>n || bylo[jaki[i+1]+k]==1)
            jaki[i]=jaki[i+1]-k;
        else{
            int k1=query(i,i+2);
            if(jaki[i+2]<jaki[i+1])
            {
                int odl=jaki[i+1]-jaki[i+2];
                if(k1==odl+k)
                    jaki[i]=jaki[i+1]+k;
                else jaki[i]=jaki[i+1]-k;
            }
            else{
                int odl=jaki[i+2]-jaki[i+1];
                if(k1==k+odl)
                    jaki[i]=jaki[i+1]-k;
                else jaki[i]=jaki[i+1]+k;
            }
        }
        bylo[jaki[i]]=1;
    }
    for(int i=1;i<=n;i++)
        answer(i,jaki[i]);
}

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