oj.uz

Submission #845937

# Submission time Handle Problem Language Result Execution time Memory
845937 2023-09-06T23:03:13 Z AlphaMale06 Xylophone (JOI18_xylophone) C++14
0 / 100
 1 ms 344 KB 
#include<bits/stdc++.h>
#include "xylophone.h"

void solve(int n){
    bool have[n+1]={0};
    int ans[n]={0};
    int mnind=n;
    int l=1; int r=n;
    int mn=1; int mx=n;
    while(l<r){
        if(r-l==1){
            int q1=query(l, n);
            int q2=query(r, n);
            if(q1>q2){
                mnind=l;
                have[1]=1;
                ans[l]=1;
            }
            else{
                mnind=r;
                have[1]=1;
                ans[r]=1;
            }
            break;
        }
        int s=(l+r)/2;
        int q1=query(s+1, r);
        if(q1!=mx-mn){
            mx=query(l, s)+1;
            r=s;
        }
        else{
            l=s+1;
        }
    }
    if(mnind!=n){
        int q=query(mnind, mnind+1);
        have[q+1]=1;
        ans[mnind+1]=q+1;
    }
    if(mnind!=1){
        int q=query(mnind-1, mnind);
        have[q+1]=1;
        ans[mnind-1]=q+1;
    }
    for(int i=mnind+2; i<=n; i++){
        int q1=query(i-1, i);
        if(q1+ans[i-1]>n || have[q1+ans[i-1]]){
            have[ans[i-1]-q1]=1;
            ans[i]=ans[i-1]-q1;
        }
        else if(ans[i-1]-q1<1 || have[ans[i-1]-q1]){
            have[ans[i-1]+q1]=1;
            ans[i]=ans[i-1]+q1;
        }
        else{
            int q2=query(i-2, i);
            if(q2==abs(ans[i-1]-ans[i-2])){
                if(ans[i-2]>ans[i-1])ans[i]=ans[i-1]+q1;
                else ans[i]=ans[i-1]-q1;
                have[ans[i]]=1;
            }
            else{
                if(ans[i-1]>ans[i-2]){
                    if(q1==q2){
                        ans[i]=ans[i-1]-q1;
                        have[ans[i]]=1;
                    }
                    else{
                        ans[i]=q1+ans[i-1];
                        have[ans[i]]=1;
                    }
                }
                else{
                    if(q1==q2){
                        ans[i]=q1+ans[i-1];
                        have[ans[i]]=1;
                    }
                    else{
                        ans[i]=ans[i-1]-q1;
                        have[ans[i]]=1;
                    }
                }
            }
        }
    }
    for(int i=mnind-2; i>=1; i--){
        int q1=query(i, i+1);
        if(q1+ans[i+1]>n || have[ans[i+1]]-q1){
            have[ans[i+1]-q1]=1;
            ans[i]=ans[i-1]+q1;
        }
        else if(ans[i+1]-q1 < 1 || have[ans[i+1-q1]]){
            have[ans[i+1]+q1]=1;
            ans[i]=ans[i+1]+q1;
        }
        else{
            int q2=query(i, i+2);
            if(q2==abs(ans[i+2]-ans[i-1])){
                if(ans[i+2]>ans[i+1])ans[i]=ans[i+1]+q1;
                else ans[i]=ans[i+1]-q1;
                have[ans[i]]=1;
            }
            else{
                if(ans[i+1]>ans[i+2]){
                    if(q1==q2){
                        ans[i]=ans[i+1]-q1;
                        have[ans[i]]=1;
                    }
                    else{
                        ans[i]=ans[i+1]+q1;
                        have[ans[i]]=1;
                    }
                }
                else{
                    if(q1==q2){
                        ans[i]=q1+ans[i+1];
                        have[ans[i]]=1;
                    }
                    else{
                        ans[i]=ans[i+1]-q1;
                        have[ans[i]]=1;
                    }
                }
            }
        }
    }
    for(int i=1; i<=n; i++){
        answer(i, ans[i]);
    }
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1 ms 344 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1 ms 344 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1 ms 344 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -