글 읽기 - 시간초과

akswnd98 4년 전 0

segment tree하고 binary search(lower bound)섞어서 nlognlogn 알고리즘 짰는데 시간초과가...

nlognlogn정도면 통과 아닌가요?

혹시 nlogn으로 푸는 방법이 있나요?

아니면 최적화가 문제인가요?

아니면 무한루프가 있나요?

정말 미치겠습니다!

use std::io;

fn init(seg: &mut Vec<i32>, node: i32, left: i32, right: i32) -> i32 {
    let mid = (left + right) / 2;

    if left == right {
        seg[node as usize] = 1;
        return seg[node as usize];
    }

   seg[node as usize] = init(seg, node * 2, left, mid) + init(seg, node * 2 + 1, mid + 1, right);

   return seg[node as usize];
}

fn update(seg: &mut Vec<i32>, node: i32, left: i32, right: i32, c: i32) {
    let mid = (left + right) / 2;

    if left > c || right < c {
        return;
    }
    if left <= c && right >= c {
        seg[node as usize] -= 1;
    }
    if left == right {
        return;
    }
    update(seg, node * 2, left, mid, c);
    update(seg, node * 2 + 1, mid + 1, right, c);
}

fn find(seg: &mut Vec<i32>, node: i32, left: i32, right: i32, c: i32) -> i32 {
    let mid = (left + right) / 2;

    if left > c {
        return 0;
    }
    if right <= c {
        return seg[node as usize];
    }
    return find(seg, node * 2, left, mid, c) + find(seg, node * 2 + 1, mid + 1, right, c);
}

fn search(seg: &mut Vec<i32>, left: i32, right: i32, c: i32, N: usize) -> i32 {
    let mid = (left + right) / 2;
    if left == right {
        return mid;
    }
    let rst = find(seg, 1, 0, N as i32 - 1, mid);
    if rst >= c {
        return search(seg, left, mid, c, N);
    } else {
        return search(seg, mid + 1, right, c, N);
    }
}

fn main() {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    let N = buf.trim_end().parse::<usize>().unwrap();
    let mut v: Vec<i32> = Vec::with_capacity(N);
    for i in 0..N {
        buf.clear();
        io::stdin().read_line(&mut buf).unwrap();
        v.push(buf.trim_end().parse::<i32>().unwrap());
    }
    v.sort();
    buf.clear();
    io::stdin().read_line(&mut buf).unwrap();
    let ar: Vec<i32> = buf.trim_end().split_whitespace().map(|s| s.parse::<i32>().unwrap()).collect();
    let mut seg: Vec<i32> = vec![0; N * 4 + 4];
    let mut mat: Vec<i32> = vec![0; N];
    init(&mut seg, 1, 0, N as i32 - 1);
    for i in (0..N).rev() {
        let search_rst = search(&mut seg, 0, N as i32 - 1, ar[i] + 1, N);
        mat[i] = search_rst;
        update(&mut seg, 1, 0, N as i32 - 1, search_rst);
    }
    for i in 0..N {
        println!("{}", v[mat[i] as usize]);
    }
}

akswnd98 4년 전 0

아 출력 병목이었습니다.

rust 쓰시는 분들 조심하세요.

println!이나 print! 호출이 100000단위가 넘어가면 무조건 병목 생깁니다.

병목 해결 소스도 같이 올려요~

use std::io;
use std::fmt::Write;

fn init(seg: &mut Vec<i32>, node: i32, left: i32, right: i32) -> i32 {
    let mid = (left + right) / 2;

    if left == right {
        seg[node as usize] = 1;
        return seg[node as usize];
    }

   seg[node as usize] = init(seg, node * 2, left, mid) + init(seg, node * 2 + 1, mid + 1, right);

   return seg[node as usize];
}

fn update(seg: &mut Vec<i32>, node: i32, left: i32, right: i32, c: i32) {
    let mid = (left + right) / 2;

    if left > c || right < c {
        return;
    }
    if left <= c && right >= c {
        seg[node as usize] -= 1;
    }
    if left == right {
        return;
    }
    update(seg, node * 2, left, mid, c);
    update(seg, node * 2 + 1, mid + 1, right, c);
}

fn find(seg: &mut Vec<i32>, node: i32, left: i32, right: i32, c: i32) -> i32 {
    let mid = (left + right) / 2;

    if left > c {
        return 0;
    }
    if right <= c {
        return seg[node as usize];
    }
    return find(seg, node * 2, left, mid, c) + find(seg, node * 2 + 1, mid + 1, right, c);
}

fn search(seg: &mut Vec<i32>, left: i32, right: i32, c: i32, N: usize) -> i32 {
    let mid = (left + right) / 2;
    if left == right {
        return mid;
    }
    let rst = find(seg, 1, 0, N as i32 - 1, mid);
    if rst >= c {
        return search(seg, left, mid, c, N);
    } else {
        return search(seg, mid + 1, right, c, N);
    }
}

fn main() {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    let N = buf.trim_end().parse::<usize>().unwrap();
    let mut v: Vec<i32> = Vec::with_capacity(N);
    for i in 0..N {
        buf.clear();
        io::stdin().read_line(&mut buf).unwrap();
        v.push(buf.trim_end().parse::<i32>().unwrap());
    }
    v.sort();
    buf.clear();
    io::stdin().read_line(&mut buf).unwrap();
    let ar: Vec<i32> = buf.trim_end().split_whitespace().map(|s| s.parse::<i32>().unwrap()).collect();
    let mut seg: Vec<i32> = vec![0; N * 4 + 4];
    let mut mat: Vec<i32> = vec![0; N];
    init(&mut seg, 1, 0, N as i32 - 1);
    for i in (0..N).rev() {
        let search_rst = search(&mut seg, 0, N as i32 - 1, ar[i] + 1, N);
        mat[i] = search_rst;
        update(&mut seg, 1, 0, N as i32 - 1, search_rst);
    }
    buf = String::with_capacity(10000000);
    for i in 0..N {
        writeln!(&mut buf, "{}", v[mat[i] as usize]);
    }
    println!("{}", buf);
}

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

문제

문제

출처

ICPC

시간초과

akswnd98 4년 전 0

akswnd98 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말