oj.uz

Submission #996130

# Submission time Handle Problem Language Result Execution time Memory
996130 2024-06-10T08:12:12 Z vjudge1 Xylophone (JOI18_xylophone) C++14
0 / 100
 0 ms 344 KB 
/*
Soln:
Find position of 1 using binary search query(i,N) == N-1
After that solve left and right parts individually

For left part for example,
A[i-1] can be easily found by 1 query
For A[j], j <= i-2, you may require 1 or 2 queries
Check abs(A[j+1]-A[j]).
You get 2 possible values of A[j]
If one of the values has already been put somewhere then we don't need any more queries
Otherwise query(j,j+2) for finding exact value.

This is <= 2n+log(n) queries for sure
but not sure why it takes <= 2n queries(or maybe it doesn't and test cases are weak)
Logically thinking it is intuitive it should take much less steps but Idk formal proof.
*/

#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i = 0; i < n; i ++)

static int A[5005];

int pos[5005];

void solve(int n) {
	if(n==1){
       answer(1,1);
    }
    else if(n==2){
        answer(1,1);
        answer(1,2);
    }
    else{
        int diff2[n+1];
        int diff1[n+1];
        for(int i=3;i<=n;i++){
            diff1[i]=query(i-1,i);
            diff2[i]=query(i-2,i);
        }
        int a[n+1];
        int dist=query(1,2);
        for(int m=-1;m<=1;m+=2){
            a[1]=1e9;
            a[2]=a[1]+m*dist;
            int Min=min(a[1],a[2]);
            for(int i=3;i<=n;i++){
                if(diff2[i]==diff1[i]+abs(a[i-2]-a[i-1])){
                    if(a[i-2]>a[i-1]){
                        a[i]=a[i-1]-diff1[i];
                    }
                    else{
                        a[i]=a[i-1]+diff1[i];
                    }
                }
                else{
                    if(a[i-2]>a[i-1]){
                        a[i]=a[i-1]+diff1[i];
                    }
                    else{
                        a[i]=a[i-1]-diff1[i];
                    }
                }
                Min=min(a[1],a[i]);
            }
            Min--;
            bool mark[n+1]={false};
            bool flag=true;
            for(int i=1;i<=n;i++){
                a[i]-=Min;
                if(a[i]>n||a[i]<=1||mark[a[i]]){
                    flag=false;
                    break;
                }
                mark[a[i]]=true;
            }
            if(flag){
                for(int i=1;i<=n;i++){
                    answer(i,a[i]);
                }
            }
        }
    }
}

Compilation message

xylophone.cpp:25:12: warning: 'A' defined but not used [-Wunused-variable]
   25 | static int A[5005];
      |            ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -