oj.uz

Submission #846108

# Submission time Handle Problem Language Result Execution time Memory
846108 2023-09-07T10:19:41 Z AlphaMale06 Xylophone (JOI18_xylophone) C++14
0 / 100
 1 ms 436 KB 
#include <bits/stdc++.h>
#include "xylophone.h"
using namespace std;

void solve(int n){
    bool have[n+1]={0};
    int ans[n+1]={0};
    int mnind=n;
    int l=1; int r=n;
    while(l<=r){
        if(l==r){
            mnind=l;
            have[1]=1;
            ans[l]=1;
            break;
        }
        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, n);
        if(q1!=n-1){
            r=s;
        }
        else{
            l=s;
        }
    }
    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;
    }
    //dobro do sad?

    for(int i=mnind+2; i<=n; i++){
        int q1=query(i-1, i);
        int hi=ans[i-1]+q1;
        int lo=ans[i-1]-q1;
        if(hi>n || have[hi]){
            have[lo]=1;
            ans[i]=lo;
        }
        else if(lo<1 || have[lo]){
            have[hi]=1;
            ans[i]=hi;
        }
        else{
            int q2=query(i-2, i);
            if(q2==abs(ans[i-1]-ans[i-2])){
                if(ans[i-1]>ans[i-2])ans[i]=lo;
                else ans[i]=hi;
                have[ans[i]]=1;
            }
            else{
                if(ans[i-1]>ans[i-2]){
                    if(q1==q2){
                        ans[i]=lo;
                        have[ans[i]]=1;
                    }
                    else{
                        ans[i]=hi;
                        have[ans[i]]=1;
                    }
                }
                else{
                    if(q1==q2){
                        ans[i]=hi;
                        have[ans[i]]=1;
                    }
                    else{
                        ans[i]=lo;
                        have[ans[i]]=1;
                    }
                }
            }
        }
    }
    for(int i=mnind-2; i>=1; i--){
        int q1=query(i, i+1);
        int hi=ans[i+1]+q1;
        int lo = ans[i+1]-q1;
        if(hi>n || have[hi]){
            have[ans[i+1]-q1]=1;
            ans[i]=lo;
        }
        else if(lo < 1 || have[lo]){
            have[hi]=1;
            ans[i]=hi;
        }
        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]=hi;
                else ans[i]=lo;
                have[ans[i]]=1;
            }
            else{
                if(ans[i+1]>ans[i+2]){
                    if(q1==q2){
                        ans[i]=lo;
                        have[ans[i]]=1;
                    }
                    else{
                        ans[i]=hi;
                        have[ans[i]]=1;
                    }
                }
                else{
                    if(q1==q2){
                        ans[i]=hi;
                        have[ans[i]]=1;
                    }
                    else{
                        ans[i]=lo;
                        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 0 ms 344 KB Output is correct
2 Correct 0 ms 356 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Incorrect 1 ms 436 KB Wrong Answer [4]
8 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

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

Subtask #3
0 / 53.0

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