Submission #445428

#	Time	Username	Problem	Language	Result	Execution time	Memory
445428		Fidisk	Xylophone (JOI18_xylophone)	C++14	100 / 100	130 ms	568 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
 
#define oo 1e9
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) (((xxxx)>>(aaaa-1))&1)
 
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<pair<int,int>,pair<int,int>> piiii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;
typedef pair<long double,long double> pld;
typedef pair<pair<long double,long double>,long double> plld;
typedef pair<long double,long long> pdl;
 
const ll base=2e9+4257;
const ll mod=998244353;
const ll mod2=1e9+4233;
const ld eps=1e-3;
const ld eps2=1e-7;
const ll maxn=1e16;
const ld pi=acos(-1);
const ll delta=1e5+7;
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
 
static int A[5000];
int ans[5009],n,i,val[5009],val2[5009];
bool chan[5009];
 
bool tryt(int x,int y) {
    int depth=0;
    int posl=0;
    int posr=0;
    ans[1]=0;
    for (i=2;i<=n;i++) {
        ans[i]=ans[i-1]+val[i-1]*y;
        if (chan[i]) y*=-1;
        depth=min(depth,ans[i]);
    }
    for (i=1;i<=n;i++) {
        ans[i]+=1-depth;
        if (ans[i]==1) {
            posl=i;
        }
        else if (ans[i]==n) {
            posr=i;
        }
    }
    if (posl<posr) {
        return true;
    }
    else {
        return false;
    }
}
 
void print() {
    for (i=1;i<=n;i++) {
        answer(i,ans[i]);
    }
}
 
void solve(int N) {
    n=N;
    for (i=1;i<=n-1;i++) {
        val[i]=query(i,i+1);
    }
    for (i=1;i<n-1;i++) {
        val2[i]=query(i,i+2);
    }
    for (i=1;i<=n-2;i++) {
        if (val[i]+val[i+1]!=val2[i]) {
            chan[i+1]=true;
        }
    }
    if (tryt(1,1)) {
        print();
    }
    else {
        tryt(1,-1);
        print();
    }
}

Compilation message (stderr)

xylophone.cpp:39:12: warning: 'A' defined but not used [-Wunused-variable]
   39 | static int A[5000];
      |            ^

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