oj.uz

Submission #232827

# Submission time Handle Problem Language Result Execution time Memory
232827 2020-05-18T10:10:46 Z Charis02 Xylophone (JOI18_xylophone) C++14
0 / 100
 5 ms 512 KB 
#include "xylophone.h"
#include<iostream>

using namespace std;

int A[5001];
bool used[5001];
int NN;

bool is_valid(int x)
{
    return (1 <= x && x<=NN && !used[x]);
}

void solve(int N)
{
    NN=N;
    int low = 1;
    int high = N-1;
    int res = 1;

    while(low <= high)
    {
        int mid = (low+high)/2;

        if(query(mid,N) == N-1)
        {
            res=max(res,mid);
            low=mid+1;
        }
        else
            high=mid-1;
    }

    used[1] = true;
    A[res] = 1;

    for(int i = res-1;i >= 1;i --)
    {
        int dif1 = query(i,i+1);

        if(!is_valid(A[i+1]+dif1))
            A[i] = A[i+1]-dif1;
        else if(!is_valid(A[i+1]-dif1))
            A[i] = A[i+1]+dif1;
        else
        {
            int dif2 = query(i,i+2);

            if(A[i+1] < A[i+2])
            {
                if(dif2 == A[i+2]-A[i+1])
                    A[i] = dif1+A[i+1];
                else if(dif2 > dif1)
                    A[i] = dif1+A[i+1];
                else
                    A[i] = A[i+1]-dif1;
            }
            else
            {
                if(dif2 == A[i+1]-A[i+2])
                    A[i] = A[i+1]-dif1;
                else if(dif2 > dif1)
                    A[i] = A[i+1]+dif1;
                else
                    A[i] = A[i+1]-dif1;
            }
        }

        used[A[i]] = true;
    }

    for(int i = res+1;i <= N;i++)
    {
        int dif1 = query(i-1,i);

        if(!is_valid(A[i-1]+dif1))
            A[i] = A[i-1]-dif1;
        else if(!is_valid(A[i-1]-dif1))
            A[i] = A[i-1]+dif1;
        else
        {
            int dif2 = query(i-2,i);

            if(A[i-1] < A[i-2])
            {
                if(dif2 == A[i-2]-A[i-1])
                    A[i] = dif1+A[i-1];
                else if(dif2 > dif1)
                    A[i] = dif1+A[i-1];
                else
                    A[i] = A[i-1]-dif1;
            }
            else
            {
                if(dif2 == A[i-1]-A[i-2])
                    A[i] = A[i-1]-dif1;
                else if(dif2 > dif1)
                    A[i] = A[i-1]+dif1;
                else
                    A[i] = A[i-1]-dif1;
            }
        }

        used[A[i]] = true;
    }

    for(int i = 1;i <= N;i++)
        answer(i,A[i]);
    return;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -