oj.uz

Submission #61935

# Submission time Handle Problem Language Result Execution time Memory
61935 2018-07-27T05:51:48 Z 노영훈(#1796) popa (BOI18_popa) C++11
61 / 100
 745 ms 708 KB 
#include "popa.h"
#include <iostream>
using namespace std;
static const int MX=1010;

int my_q(int x, int l, int r){
    return query(x,x,l,r);
}

static int n;

int find_l(int x){
    int s=0, e=x;
    while(s<e){
        int m=(s+e)/2;
        if(my_q(x,m,x)) e=m;
        else s=m+1;
    }
    return s;
}

int find_r(int x){
    int s=x, e=n-1;
    while(s<e){
        int m=(s+e+1)/2;
        if(my_q(x,x,m)) s=m;
        else e=m-1;
    }
    return s;
}
static int Lidx[MX]={}, Ridx[MX]={};
static int *Lson, *Rson;

static int solve(int s, int e){
    if(e<s) return -1;
    for(int i=s; i<=e; i++){
        if(Lidx[i]<=s && e<=Ridx[i]){
            Lson[i]=solve(s,i-1);
            Rson[i]=solve(i+1,e);
            if(Lson[i]==-2 || Rson[i]==-2) continue;
            return i;
        }
    }
    return -2;
}

int solve(int N, int _Lson[], int _Rson[]){
    n=N; Lson=_Lson, Rson=_Rson;
    for(int i=0; i<n; i++){
        Lidx[i]=find_l(i);
        Ridx[i]=find_r(i);
    }
    return solve(0,n-1);
}

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 380 KB Output is correct
2 Correct 27 ms 472 KB Output is correct
3 Correct 57 ms 472 KB Output is correct
4 Correct 29 ms 528 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 669 ms 580 KB Output is correct
2 Correct 745 ms 708 KB Output is correct
3 Correct 539 ms 708 KB Output is correct
4 Correct 669 ms 708 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 708 KB too many queries
2 Halted 0 ms 0 KB -