oj.uz

Submission #874368

# Submission time Handle Problem Language Result Execution time Memory
874368 2023-11-16T18:52:27 Z AlphaMale06 Xylophone (JOI18_xylophone) C++14
0 / 100
 1 ms 344 KB 
#include <bits/stdc++.h>
#include "xylophone.h"

using namespace std;

void solve(int n){
    bool have[n+1]={0};
    int a[n+1]={0};
    int mn;
    int l=1;
    int r=n-1;
    while(l<=r){
        int s=(l+r)/2;
        if(query(s+1, n)==n-1){
            l=s+1;
        }
        else{
            r=s-1;
        }
    }
    mn=l;
    cout << mn << '\n';
    have[1]=1;
    int nxt=1+query(mn, mn+1);
    a[mn]=1;
    a[mn+1]=nxt;
    have[nxt]=1;
    if(mn!=1){
        int prv=1+query(mn-1, mn);
        a[mn-1]=prv;
        have[prv]=1;
    }
    for(int i=mn+2; i<=n; i++){
        int q1=query(i-1, i);
        int pos1=a[i-1]+q1;
        int pos2=a[i-1]-q1;
        if(pos1<=0 || pos1>n || have[pos1]){
            a[i]=pos2;
        }
        else if(pos2<=0 || pos2>n || have[pos2]){
            a[i]=pos1;
        }
        else{
            int q2=query(i-2, i);
            if(q2==q1 || q2==abs(a[i-1]-a[i-2])){
                if(a[i-1]>a[i-2]){
                    a[i]=pos2;
                }
                else{
                    a[i]=pos1;
                }
            }
            else{
                if(a[i-1]>a[i-2]){
                    a[i]=pos1;
                }
                else a[i]=pos2;
            }
        }
    }
    for(int i=mn-2; i>=1; i--){
        int q1=query(i, i+1);
        int pos1=a[i+1]+q1;
        int pos2=a[i+1]-q1;
        if(pos1<=0 || pos1>n || have[pos1]){
            a[i]=pos2;
        }
        else if(pos2<=0 || pos2>n || have[pos2]){
            a[i]=pos1;
        }
        else{
            int q2=query(i-2, i);
            if(q2==q1 || q2==abs(a[i-1]-a[i-2])){
                if(a[i-1]>a[i-2]){
                    a[i]=pos2;
                }
                else{
                    a[i]=pos1;
                }
            }
            else{
                if(a[i-1]>a[i-2]){
                    a[i]=pos1;
                }
                else a[i]=pos2;
            }
        }
    }
    for(int i=1; i<=n; i++){
        answer(i, a[i]);
    }

}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 344 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 344 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 344 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -