제출 #555772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
555772		urosk	Xylophone (JOI18_xylophone)	C++14	47 / 100	103 ms	864 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;
    a[tr] = n;
    a[tr-1] = n - get(tr-1,tr);
    if(tr<n) a[tr+1] = n - get(tr,tr+1);
    for(int i = tr-2;i>=1;i--){
        if(a[i]!=0) continue;
        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;
        }
    }
    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(a[i]!=0) continue;
        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
*/

컴파일 시 표준 에러 (stderr) 메시지

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:47:31: warning: 'rez' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |     if(tr<n) a[tr+1] = n - get(tr,tr+1);
      |                            ~~~^~~~~~~~~

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