Làm sao để dùng mảng char 10^6 kí tự trong C mà không bị Time Limit Exceeded

#1

Em có 1 bài tập về chuỗi dưới 10^6 kí tự nhưng khi nộp bài bằng C thì bị TLE
còn nộp bằng C O2 thì AC
các bro cho em hỏi có cách nào nộp bằng C mà vẫn AC không ạ?

đề bài đây ạ: https://luyencode.net/problem/UPWORD

#2

Không có đề bài thì không đánh giá được gì hết nhé bạn.

3 Likes
#3

Bài này chỉ cần giải trong O(n) là thừa sức Accepted, không cần kỹ năng gì cao siêu để lưu string cả. Thậm chí nếu thích thì bạn cũng không cần dùng xâu :popcorn:

1 Like
#4

code em đây ạ, em dùng C O2 thì chạy có 7ms thôi ạ nhưng dùng C thì nó TLE 2 case cuối nên em muốn hỏi có cách nào nhập vào bằng string mà không bị TLE á

#include <stdio.h>
#include <string.h>
int main(){
    int count=0;
    char c[1000000];
    scanf("%s",c);
    for(int i =0;i<strlen(c);i++){
        if(c[i]>='A' && c[i]<='Z' && (c[i+1]<'A' || c[i+1]>'Z')){
            ++count;
        }
    }
    printf("%d",count);
}
#5

Do bạn khai báo mảng c trong hàm main() nên mảng c nằm trên bộ nhớ stack (vốn có kích cỡ rất bé, khoảng vài KB), còn mảng 1e6 kí tự có kích cỡ khoảng 0.95MB nên xảy ra tình trạng stack overflow. Bạn có 3 lựa chọn:

  1. cấp phát động 1 mảng 1 triệu kí tự trong main().
  2. đưa mảng c ra ngoài main(), biến nó thành global variable.
  3. tìm cách không dùng mảng nữa.
1 Like
#6

Em đưa mảng ra ngoài thành global variable nhưng vẫn TLE 2 case cuối ạ

image
image1101×500 21.5 KB

#7

Bạn hãy nói rõ code của bạn bị TLE (time limit exceeded, nhấn mạnh vào time), vì các verdict chứa từ “limit” còn có MLE (memory limit exceeded) hoặc tệ hơn là output limit exceeded. Nãy giờ bạn nói mà mình không hiểu bạn nói “limit” là gì cho đến khi bạn chụp verdict của 2 test cuối.

Vậy có lẽ bạn cần dùng cách bỏ char[], vì đọc 1 mảng char cũng tốn kha khá thời gian.

#8

trên subject em có ghi là Time Limit Exceeded rồi á a :sweat_smile:

#9

Mình không chỉ đọc title mà đọc cả các comment của bạn nữa, mình cảm thấy không rõ ràng, vậy thôi. Dân CP gọi AC, WA, TLE, RTE, MLE chứ chẳng ai gọi acpt, limit cả.

2 Likes
#10

Em đã sửa rồi ạ, em cảm ơn a

#11

Bạn có dùng đến hàm strlen là xem như cho nó lặp thêm 1 lần nữa rồi, tối ưu điều kiện lặp chuỗi xem sao.

3 Likes
#12

Đã AC rồi ạ! Cảm ơn bro :smile:

#13

đề bài đã hỏng link rồi .

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?