Submission #1235420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235420		CELD_07	Xylophone (JOI18_xylophone)	C++20	47 / 100	24 ms	484 KiB

xylophone

#include "xylophone.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define vll vector<ll>
#define sd second
#define ft first
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 1000000007
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
#define inf (ll)1e15
#define db(x) cout<<#x<<" : "<<x<<endl;
#define PRESICION(x) cout.setf(ios::fixed,ios::floatfield); cout.precision(x);
using namespace std;
using namespace __gnu_pbds;
ll dx[]={1, -1, 0, 0};
ll dy[]={0, 0, 1, -1};
inline ll sm(ll a, ll b){
return ((a%mod)+(b%mod))%mod;
}
inline ll ml(ll a, ll b){
return ((a%mod)*(b%mod))%mod;
}
inline ll rs(ll a, ll b){
return ((a%mod)-(b%mod)+mod)%mod;
}
ll bpow(ll a , ll b) {
if (b==0)return 1;
if (b%2!=0)return ((bpow(a, b-1)%mod)*(a%mod))%mod;
ll r=bpow (a ,b/ 2) ;
return ((r%mod)*(r%mod))%mod;
}
inline ll q(vector<ll>& v, ll o, bool n){
return (n==0 ? max({v[o], v[o+1], v[o+2]})-min({v[o], v[o+1], v[o+2]}) : max({v[o], v[o-1], v[o-2]})-min({v[o], v[o-1], v[o-2]}));
}
void solve(int N) {
vector<ll> res(N+1, -1), res1(N+1, -1);
ll tl=1, tr=N, r=N, r1=1;
while(tl<=tr){
ll tm=(tl+tr)/2;
if(query(1, tm)==N-1){tr=tm-1;r=tm;}
else tl=tm+1;
}
res1[r]=N;
res1[r-1]=N-query(r-1, r);
if(r!=N)res1[r+1]=N-query(r, r+1);
for(ll i=r-2; i>=1; i--){
ll o=query(i, i+1);
if(res[res1[i+1]-o]==1){res1[i]=res1[i+1]+o;res[res1[i]]=1;continue;}
else if(res[res1[i+1]+o]==1){res1[i]=res1[i+1]-o;res[res1[i]]=1;continue;}
ll o2=query(i, i+2);
res1[i]=res1[i+1]-o;
if(o2==q(res1, i, 0))res1[i]=res1[i+1]-o;
else res1[i]=res1[i+1]+o;
}
for(ll i=r+2; i<=N; i++){
ll o=query(i-1, i);
if(res[res1[i-1]-o]==1){res1[i]=res1[i-1]+o;res[res1[i]]=1;continue;}
else if(res[res1[i-1]+o]==1){res1[i]=res1[i-1]-o;res[res1[i]]=1;continue;}
ll o2=query(i-2, i);
res1[i]=res1[i-1]-o;
if(o2==q(res1, i, 1))res1[i]=res1[i-1]-o;
else res1[i]=res1[i-1]+o;
}
for(int i=1; i<=N; i++){
answer(i, res1[i]);
}
}

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