글 읽기 - 음주 코딩 질문드립니다

euphoric_n 2년 전 0

아무리 살펴봐도 잘못된 부분을 찾을 수 없어 질문드리게 되었습니다

부호만 구하면 되기 때문에 모든 음수는 -1, 양수는 1로 바꿔서 세그먼트 트리에 저장합니다.

예를들어 n=4일 때 값들은 아래 그림과 같이 tree[4] ~ tree[7]에 저장됩니다.

아래 그림에서 tree[1]은 tree[2] * tree[3]의 값을 가지고,

tree[2] 는 tree[4] * tree[5], tree[3] 은 tree[6] * tree[7]의 값을 가지므로 tree[1]은 모든 원소의 곱을 가지고 있습니다.

tree[1]

tree[2] tree[3]

tree[4] tree[5] tree[6] tree[7]

init 함수

세그먼트 트리 초기화시 start = 0, end = n-1, node = 1 값을 인자로 하여 init 함수를 호출합니다.

start와 end는 초기화하고자 하는 arr 인덱스, node는 tree에서의 인덱스입니다.

start와 end가 같아지면 해당 노드에 arr 배열의 값을 저장하면서 해당 값을 반환, (tree[node] = arr[start])

그렇지 않다면 왼쪽과 오른쪽으로 나눠 초기화 하면서 양쪽의 값을 곱해서 현재 위치에 저장합니다.

update 함수

start, end, node, index, dif를 인자로 가집니다.

index는 업데이트하고자 하는 수의 arr 인덱스입니다. (i번째 수라면 i-1)

dif는 덮어쓰고자 하는 값입니다.

index가 [start, end] 범위내에 있지 않다면 단순히 해당 위치의 tree[node] 값을 반환합니다. (업데이트 시 필요)

start == end == index라면 해당 노드에 dif 값을 저장하고 반환합니다. ( return tree[node] = dif )

그렇지 않다면 왼쪽과 오른쪽으로 나눠 업데이트하면서 현재 노드의 값도 업데이트합니다.

answer 함수

[left, right] 범위의 곱을 구하려 합니다.

해당 범위가 [start, end]와 겹치지 않는다면 1을 반환합니다. (곱셈의 항등원)

만약 해당 범위가 [start, end]를 완전히 포함한다면 현재 노드의 값을 반환합니다.

그렇지 않다면 [start, mid], [mid+1, end]로 나누어 양쪽 노드의 값을 곱한 값을 반환합니다.

문제 예제 입출력과 출처인 대회 입출력 데이터는 통과했습니다. 제출시에는 50%에서 WA를 받습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <fstream>

const std::string str[3] = {"-", "0", "+"};

int convert(int a) {
    if(a > 0) return 1;
    if(a < 0) return -1;
    return 0;
}

int init(int *tree, int *arr, int start, int end, int node) {
    if(start == end) return tree[node] = arr[start];
    int mid = (start + end)/2;
    return tree[node] = init(tree, arr, start, mid, node*2) * init(tree, arr, mid+1, end, node*2+1);
}

int update(int *tree, int start, int end, int node, int index, int dif) {
    if(index < start || end < index) return tree[node];
    if(start == end && start == index) return tree[node] = dif;
    else {
        int mid = (start + end)/2;
        return tree[node] = update(tree, start, mid, node*2, index, dif) * update(tree, mid+1, end, node*2+1, index, dif);
    }
}

int answer(int *tree, int start, int end, int left, int right, int node) {
    if(end < left || start > right) return 1;
    if(left <= start && end <= right) return tree[node];
    int mid = (start + end)/2;
    return answer(tree, start, mid, left, right, node*2) * answer(tree, mid+1, end, left, right, node*2+1);
}

void show(int *tree, int n) {
    int cursor = 1;
    int h = (int)ceil(log2(n));
    for(int i=0; i<=h; i++) {
        for(int j=0; j<(1 << i); j++) {
            std::cout << tree[cursor++] << " ";
        }
        std::cout << "\n";
    }
}

int main() {
    std::cin.tie(0);
    std::iostream::sync_with_stdio(0);
    // std::ifstream is;
    // is.open("BOJ/input.txt");
    auto &is = std::cin;
    bool first = true;
    while(!is.eof()) {
        if(!first) std::cout << "\n";
        else first = false;
        int n, k;
        is >> n >> k;
        int *arr = new int[n];
        for(int i=0; i<n; i++) {
            is >> arr[i];
            arr[i] = convert(arr[i]);
        }
        int *tree = new int[1 << ((int)ceil(log2(n)) + 1)];
        std::string results = "";
        std::string slow_results = "";
        init(tree, arr, 0, n-1, 1);
        // show(tree, n);
        for(int i=0; i<k; i++) {
            char op;
            int a, b;
            is >> op >> a >> b;
            if(op == 'C') {
                update(tree, 0, n-1, 1, a-1, convert(b));
                arr[a-1] = convert(b);
            } else {
                results += str[answer(tree, 0, n-1, a-1, b-1, 1)+1];
                /*
                int tmp = 1;
                for(int z=a-1; z<=b-1; z++) {
                    tmp *= arr[z];
                }
                slow_results += str[tmp+1];
                */
            }
            // show(tree, n);
        }
        /*
        if(results != slow_results) {
            std::cout << "FAILED\n";
            std::cout << results << std::endl;
            std::cout << slow_results << std::endl;
        } else {
            std::cout << "PASS\n";
        }
        */
        delete[] arr;
        delete[] tree;
    }
    return 0;
}

seastar105 2년 전 0

입력부분을 바꾸니 맞네요

저도 정확히 기억하고 있는 건 아닌데 cin.eof()가 예상대로 동작을 안하나 봅니다. 아래 코드처럼 바꿔주시면 동작합니다. cin이 아마 입력을 받으면 1을 리턴해주고 아니라면 0을 리턴해주는 것으로 어디서 들어서 이게 잘 동작합니다.

auto &is = std::cin;
bool first = true;
while(!is.eof()) {
    if(!first) std::cout << "\n";
    else first = false;
    int n, k;
    is >> n >> k;
    
위 입력부를 아래로 바꾸니 통과합니다.
auto &is = std::cin;
bool first = true;
int n, k;
while(is >> n >> k) {
    if(!first) std::cout << "\n";
    else first = false;

euphoric_n 2년 전 0

답변 감사드립니다. eof 함수 한번 확인해봐야겠네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

음주 코딩 질문드립니다

euphoric_n 2년 전 0

seastar105 2년 전 0

euphoric_n 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말