Submission #114980

#	Time	Username	Problem	Language	Result	Execution time	Memory
114980		IVIosab	Xylophone (JOI18_xylophone)	C++17	100 / 100	108 ms	1088 KiB

xylophone

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

int a[5005];
int a1[5005],a2[5005];

void solve(int N) {
    int n=N;
    int value = n-1;
    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;
        }
    }
    a1[1]=0;
    a2[1]=0;
    int mn1=0,mn2=0;
    for(int i=2;i<=n;i++){
        int t=mp[{i-1,i}];
        if(i==2){
            a1[i]=mp[{1,2}];
            a2[i]=-mp[{1,2}];
        }
        else{
            if(mp[{i-2,i}]){
                if(a1[i-2]>a1[i-1]){
                    a1[i]=a1[i-1]-t;
                }
                else{
                    a1[i]=a1[i-1]+t;
                }
                if(a2[i-2]>a2[i-1]){
                    a2[i]=a2[i-1]-t;
                }
                else{
                    a2[i]=a2[i-1]+t;
                }
            }
            else{
                if(a1[i-2]>a1[i-1]){
                    a1[i]=a1[i-1]+t;
                }
                else{
                    a1[i]=a1[i-1]-t;
                }
                if(a2[i-2]>a2[i-1]){
                    a2[i]=a2[i-1]+t;
                }
                else{
                    a2[i]=a2[i-1]-t;
                }
            }
        }
        mn1=min(mn1,a1[i]);
        mn2=min(mn2,a2[i]);
    }
    int m1=1e9,mx1=0,m2=1e9,mx2=0,im1=0,ix1=0,im2=0,ix2=0;
    for(int i=1;i<=n;i++){
        a1[i]+=abs(mn1)+1;
        a2[i]+=abs(mn2)+1;
        if(a1[i]<m1){
            m1=a1[i];
            im1=i;
        }
        if(a1[i]>mx1){
            mx1=a1[i];
            ix1=i;
        }
    }
    if(im1<ix1){
        for(int i=1;i<=n;i++){
            answer(i,a1[i]);
        }
    }
    else{
        for(int i=1;i<=n;i++){
            answer(i,a2[i]);
        }
    }
}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:10:9: warning: unused variable 'value' [-Wunused-variable]
     int value = n-1;
         ^~~~~
xylophone.cpp:64:22: warning: unused variable 'm2' [-Wunused-variable]
     int m1=1e9,mx1=0,m2=1e9,mx2=0,im1=0,ix1=0,im2=0,ix2=0;
                      ^~
xylophone.cpp:64:29: warning: unused variable 'mx2' [-Wunused-variable]
     int m1=1e9,mx1=0,m2=1e9,mx2=0,im1=0,ix1=0,im2=0,ix2=0;
                             ^~~
xylophone.cpp:64:47: warning: unused variable 'im2' [-Wunused-variable]
     int m1=1e9,mx1=0,m2=1e9,mx2=0,im1=0,ix1=0,im2=0,ix2=0;
                                               ^~~
xylophone.cpp:64:53: warning: unused variable 'ix2' [-Wunused-variable]
     int m1=1e9,mx1=0,m2=1e9,mx2=0,im1=0,ix1=0,im2=0,ix2=0;
                                                     ^~~

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