Submission #555755

#	Time	Username	Problem	Language	Result	Execution time	Memory
555755		urosk	Xylophone (JOI18_xylophone)	C++14	47 / 100	92 ms	936 KiB

xylophone

#include "xylophone.h"
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;
static int A[5000];
#define maxn 5005
int a[maxn];
map<pii,int> mp;
int get(int l,int r){
    if(mp.count({l,r})) return mp[{l,r}];
    return mp[{l,r}] = query(l,r);
}

void solve(int N) {

	int n = N;
    int l = 1,r = n,mid,rez;
    while(l<=r){
        mid = (l+r)/2;
        int e = get(1,mid);
        if(e<n-1){
            l = mid+1;
        }else{
            r = mid-1;
            rez = mid;
        }
    }
    int tr = rez;
    l = 1,r = tr-1,mid,rez = -1;
    while(l<=r){
        mid = (l+r)/2;
        if(get(mid,tr)<n-1){
            r = mid-1;
        }else{
            l = mid+1;
            rez = mid;
        }
    }
    int tl = rez;
    a[tl] = 1;
    a[tr] = n;
    //cerr<<tl<< " "<<tr<<endl;
    if(tl>1) a[tl-1] = 1 + query(tl-1,tl);
    for(int i = tl-2;i>=1;i--){
        int x = get(i,i+1);
        int y = get(i+1,i+2);
        int z = get(i,i+2);
        if(x+y==z){
            if(a[i+1]>=a[i+2]) a[i] = a[i+2] + z;
            else a[i] = a[i+2] - z;
        }else if(z==x){
            if(a[i+1]>=a[i+2]) a[i] = a[i+1] - x;
            else a[i] = a[i+1] + x;
        }else{
            if(a[i+1]>=a[i+2]) a[i] = a[i+1] - x;
            else a[i] = a[i+1] + x;
        }
    }
    if(tl<n&&tl+1!=tr) a[tl+1] = a[tl] + query(tl,tl+1);
    for(int i = tl+2;i<tr;i++){
        int x = get(i-1,i);
        int y = get(i-2,i-1);
        int z = get(i-2,i);
        //cerr<<x<< " "<<y<<" "<<z<<endl;
        if(x+y==z){
            if(a[i-1]>=a[i-2]) a[i] = a[i-2] + z;
            else a[i] = a[i-2] - z;
        }else if(z==x){
            if(a[i-1]>=a[i-2]) a[i] = a[i-1] - x;
            else a[i] = a[i-1] + x;
        }else{
            if(a[i-1]>=a[i-2]) a[i] = a[i-1] - x;
            else a[i] = a[i-1] + x;
        }
    }
    if(tr<n) a[tr+1] = a[tr] - query(tr,tr+1);
    for(int i = tr+2;i<=n;i++){
        int x = get(i-1,i);
        int y = get(i-2,i-1);
        int z = get(i-2,i);
        if(x+y==z){
            if(a[i-1]>=a[i-2]) a[i] = a[i-2] + z;
            else a[i] = a[i-2] - z;
        }else if(z==x){
            if(a[i-1]>=a[i-2]) a[i] = a[i-1] - x;
            else a[i] = a[i-1] + x;
        }else{
            if(a[i-1]>=a[i-2]) a[i] = a[i-1] - x;
            else a[i] = a[i-1] + x;
        }
    }
    //ceri(a,1,n);
    for(int i = 1;i<=n;i++) answer(i,a[i]);
}
/*
5
2 1 5 3 4
*/

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:45:31: warning: right operand of comma operator has no effect [-Wunused-value]
   45 |     l = 1,r = tr-1,mid,rez = -1;
      |                               ^
xylophone.cpp: At global scope:
xylophone.cpp:21:12: warning: 'A' defined but not used [-Wunused-variable]
   21 | static int A[5000];
      |            ^
xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:92:28: warning: 'rez' may be used uninitialized in this function [-Wmaybe-uninitialized]
   92 |     if(tr<n) a[tr+1] = a[tr] - query(tr,tr+1);
      |                        ~~~~^

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