Submission #788003

# Submission time Handle Problem Language Result Execution time Memory
788003 2023-07-19T16:03:13 Z Rafi22 Xylophone (JOI18_xylophone) C++14
0 / 100
1 ms 208 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,i+1);
        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,i+2);
            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);
      |                       ~~~~~^~~~~~~
# 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 208 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -
# 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 208 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -
# 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 208 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -