Submission #590452

#	Time	Username	Problem	Language	Result	Execution time	Memory
590452		abcvuitunggio	Xylophone (JOI18_xylophone)	C++17	100 / 100	105 ms	596 KiB

xylophone

#include "xylophone.h"
#include <set>
using namespace std;
void solve(int n){
    int a[n+1],b[n+1],c[n+1];
    for (int i=0;i<=n;i++){
        a[i]=0;
        b[i]=0;
        c[i]=0;
    }
    for (int i=1;i+1<=n;i++)
        a[i]=query(i,i+1);
    for (int i=1;i+2<=n;i++){
        int val=query(i,i+2);
        b[i+1]=(a[i]+a[i+1]==val?1:-1);
    }
    int d=1,mx=0,mn=0;
    set <int> s;
    s.insert(0);
    for (int i=2;i<=n;i++){
        c[i]=c[i-1]+d*a[i-1];
        d*=b[i];
        s.insert(c[i]);
        mx=max(mx,c[i]);
        mn=min(mn,c[i]);
    }
    if (s.size()==n&&mx-mn+1==n){
        int ch=0;
        for (int i=1;i<=n;i++){
            c[i]-=mn-1;
            if (c[i]==1)
                ch=1;
            if (c[i]==n)
                if (!ch)
                    break;
        }
        if (ch){
            for (int i=1;i<=n;i++)
                answer(i,c[i]);
            return;
        }
    }
    c[1]=0;
    d=-1;
    mn=0;
    for (int i=2;i<=n;i++){
        c[i]=c[i-1]+d*a[i-1];
        d*=b[i];
        mn=min(mn,c[i]);
    }
    for (int i=1;i<=n;i++)
        answer(i,c[i]-mn+1);
}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:27:17: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |     if (s.size()==n&&mx-mn+1==n){
      |         ~~~~~~~~^~~

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