Submission #988343

#	Time	Username	Problem	Language	Result	Execution time	Memory
988343		Yahia_Emara	Xylophone (JOI18_xylophone)	C++14	100 / 100	63 ms	744 KiB

xylophone

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define LOOP(n) for(int rp=0;rp<(n);rp++)
#define sz(x) int(x.size())
#define bk(x) x.back()
#define dbg(x) cout << (#x) << " : " << x << endl
#define sdbg(x) cout << (#x) << " : " << x << "\n"
#define dbeg(x) cout << (#x) << " : " << x << ", "
#define sq(x) ((x)*(x))
#define lsb(x) ((x)&(-(x)))
#define sqm(x) mul((x),(x))
#define isnp(x) ((x)&((x)-1))
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
#define fsh cout.flush()
using namespace std;
using namespace __gnu_pbds;
#define OS tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define ofk order_of_key
//#pragma GCC optimize("trapv")
#pragma GCC optimize("Ofast","unroll-loops","O3")
#pragma GCC target("popcnt")
mt19937_64 rng(time(0));
int rnd(int l,int r){
    return uniform_int_distribution<int>(l,r)(rng);
}
typedef long long ll;
typedef long double dl;
typedef unsigned long long ull;
const int SZ=2e5+7,MSZ=3e4+7;
const ll INF=1e18+7;
const dl eps=1e-18;
int MOD=1e9+7;
ll trig(ll n){
    return n*(n+1)/2;
}
int getN(){
    int n;cin >> n;
    return n;
}
#include "xylophone.h"
//#include "grader.cpp"
void solve(int n){
    int a[n]{},b[n]{},pa[n],pb[n];
    a[1]=query(1,2),b[1]=-a[1];
    int si=1;
    for(int i=2;i<n;i++){
        a[i]=query(i,i+1);
        if(query(i-1,i+1)!=abs(a[i-1])+a[i])si*=-1;
        a[i]*=si;
        b[i]=-a[i];
    }
    int Ma=0,Mb=0;
    for(int i=1;i<n;i++)a[i]+=a[i-1],b[i]+=b[i-1],Ma=min(Ma,a[i]),Mb=min(Mb,b[i]);
    for(int i=0;i<n;i++)a[i]-=Ma,b[i]-=Mb;
    for(int i=0;i<n;i++)pa[a[i]]=i,pb[b[i]]=i;
    if(pa[0]>pa[n-1])LOOP(n)swap(a[rp],b[rp]);
    else if(pb[0]<pb[n-1]){
        for(int i=0;i<n;i++){
            int mxa=0,mna=1e9,mxb=0,mnb=1e9;
            for(int j=i;j<n;j++){
                mxa=max(mxa,a[j]),mxb=max(mxb,b[j]);
                mna=min(mna,a[j]),mnb=min(mnb,b[j]);
                if(mxa-mna!=mxb-mnb){
                    int Z=query(i+1,j+1);
                    if(Z==mxa-mna)goto ptr2;
                    if(Z==mxb-mnb)goto ptr;
                    assert(0);
                }
            }
        }
        assert(0);
        ptr:LOOP(n)swap(a[rp],b[rp]);
        ptr2:;
    }
    for(int i=0;i<n;i++)answer(i+1,a[i]+1);
}

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