oj.uz

Submission #787990

# Submission time Handle Problem Language Result Execution time Memory
787990 2023-07-19T15:53:28 Z Rafi22 Xylophone (JOI18_xylophone) C++14
0 / 100
 1 ms 300 KB 
#include <bits/stdc++.h>
#include "xylophone.h"

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=5007;

int a[N];
bool is[N];

void Set(int i,int x)
{
    a[i]=x;
    is[x]=1;
}

void solve(int n)
{
    int l=1,r=n,sr,k;
    while(l<=r)
    {
        sr=(l+r)/2;
        if(query(sr,n)==n-1)
        {
            k=sr;
            l=sr+1;
        }
        else r=sr-1;
    }
    Set(k,1);
    if(k+1<=n) Set(k+1,query(k,k+1)+1);
    for(int i=k+2;i<=n;i++)
    {
        int d=query(i-1,i);
        if(a[i-1]-d<1||is[a[i-1]-d]) Set(i,a[i-1]+d);
        else if(a[i-1]+d>n||is[a[i-1]+d]) Set(i,a[i-1]-d);
        else
        {
            int l=query(i-2,i);
            if(l==abs(a[i-1]-a[i-2]))
            {
                if(a[i-2]<a[i-1]) Set(i,a[i-1]-d);
                else Set(i,a[i-1]+d);
            }
            else
            {
                if(a[i-2]<a[i-1]) Set(i,a[i-1]+d);
                else Set(i,a[i-1]-d);
            }
        }
    }
    if(k-1>0) Set(k-1,query(k-1,k)+1);
    for(int i=k-2;i>0;i--)
    {
        int d=query(i+1,i);
        if(a[i+1]-d<1||is[a[i+1]-d]) Set(i,a[i+1]+d);
        else if(a[i+1]+d>n||is[a[i+1]+d]) Set(i,a[i+1]-d);
        else
        {
            int l=query(i+2,i);
            if(l==abs(a[i+1]-a[i+2]))
            {
                if(a[i+2]<a[i+1]) Set(i,a[i+1]-d);
                else Set(i,a[i+1]+d);
            }
            else
            {
                if(a[i+2]<a[i+1]) Set(i,a[i+1]+d);
                else Set(i,a[i+1]-d);
            }
        }
    }
    for(int i=1;i<=n;i++) answer(i,a[i]);
}
/*
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve()




    return 0;
}*/

Compilation message

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:63:28: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |     if(k-1>0) Set(k-1,query(k-1,k)+1);
      |                       ~~~~~^~~~~~~

Subtask #1
0 / 11.0

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

Subtask #2
0 / 36.0

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

Subtask #3
0 / 53.0

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