oj.uz

답안 #70035

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
70035 2018-08-22T09:36:22 Z 3zp popa (BOI18_popa) C++14
61 / 100
 243 ms 708 KB 
#include<bits/stdc++.h>
#include "popa.h"
using namespace std;
int l[1009], r[1009], A[1009];
/*bool query(int a, int b, int c, int d){
    int gcd1 = 0, gcd2 = 0;
    for(int i = a; i <= b; i++)
        gcd1 = __gcd(gcd1, A[i]);
    for(int i = c; i <= d; i++)
        gcd2 = __gcd(gcd2, A[i]);
    return gcd1 == gcd2;
}*/
int SOLVE(int le, int ri, int *Left, int *Right){
    if(le > ri) return -1;
    for(int i = le; i <= ri; i++){
        if(l[i] <= le && r[i] >= ri){
            int A = SOLVE(le, i - 1, Left, Right);
            int B = SOLVE(i + 1, ri, Left, Right);
            Left[i] = A;
            Right[i] = B;
            return i;
        }
    }
}
int solve(int N, int* Left, int* Right){
    stack<int> S;
    for(int i = 0; i < N; i++){
        while(S.size() && query(S.top(), i,i,i)){
            S.pop();
        }
        if(!S.size()) l[i] = 0;
        else l[i] = S.top() + 1;
        S.push(i);
    }
    while(S.size()) S.pop();
    for(int i = N - 1; i >= 0; i--){
        while(S.size() && query(i ,S.top(),i,i)){
            S.pop();
        }
        if(!S.size()) r[i] = N - 1;
        else r[i] = S.top() - 1;
        S.push(i);
    }
    return SOLVE(0, N - 1, Left, Right);

}

Compilation message

popa.cpp: In function 'int SOLVE(int, int, int*, int*)':
popa.cpp:24:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 248 KB Output is correct
2 Correct 21 ms 388 KB Output is correct
3 Correct 30 ms 388 KB Output is correct
4 Correct 30 ms 420 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 190 ms 508 KB Output is correct
2 Correct 166 ms 624 KB Output is correct
3 Correct 134 ms 704 KB Output is correct
4 Correct 243 ms 708 KB Output is correct

Subtask #3
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 708 KB too many queries
2 Halted 0 ms 0 KB -