oj.uz

답안 #232010

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
232010 2020-05-15T17:11:25 Z alexandra_udristoiu Xylophone (JOI18_xylophone) C++14
0 / 100
 5 ms 384 KB 
#include<iostream>
#include "xylophone.h"
using namespace std;
static int v[5005], viz[5005], dif[5005];

void solve(int n) {
    int i, st, dr, mid, d, d3, p;
    st = 1;
    dr = n;
    while(st <= dr){
        mid = (st + dr) / 2;
        if(query(mid, n) == n - 1){
            st = mid + 1;
        }
        else{
            dr = mid - 1;
        }
    }
    p = dr;
    v[p] = viz[1] = 1;
    for(i = p - 1; i >= 1; i--){
        d = query(i, i + 1);
        if(v[i + 1] - d < 1 || viz[ v[i + 1] - d ] == 1){
            v[i] = v[i + 1] + d;
        }
        else{
            if(v[i + 1] + d > n || viz[ v[i + 1] + d ] == 1){
                v[i] = v[i + 1] - d;
            }
            else{
                d3 = query(i, i + 2);
                if(d3 == d + dif[i + 1]){
                    if(v[i + 2] > v[i + 1]){
                        v[i] = v[i + 1] - d;
                    }
                    else{
                        v[i] = v[i + 1] + d;
                    }
                }
                else{
                    if(v[i + 2] > v[i + 1]){
                        v[i] = v[i + 1] - d;
                    }
                    else{
                        v[i] = v[i + 1] + d;
                    }
                }
            }
        }
        dif[i] = d;
        viz[ v[i] ] = 1;
    }
    for(i = p + 1; i <= n; i++){
        d = query(i - 1, i);
        if(v[i - 1] - d < 1 || viz[ v[i - 1] - d ] == 1){
            v[i] = v[i - 1] + d;
        }
        else{
            if(v[i - 1] + d > n || viz[ v[i - 1] + d ] == 1){
                v[i] = v[i - 1] - d;
            }
            else{
                d3 = query(i - 2, i);
                if(d3 == d + dif[i - 1]){
                    if(v[i - 2] > v[i - 1]){
                        v[i] = v[i - 1] - d;
                    }
                    else{
                        v[i] = v[i - 1] + d;
                    }
                }
                else{
                    if(v[i - 2] > v[i - 1]){
                        v[i] = v[i - 1] - d;
                    }
                    else{
                        v[i] = v[i - 1] + d;
                    }
                }
            }
        }
        dif[i] = d;
        viz[ v[i] ] = 1;
    }
    for(i = 1; i <= n; i++){
        answer(i, v[i]);
    }
    return;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Incorrect 5 ms 384 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Incorrect 5 ms 384 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Incorrect 5 ms 384 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -