Lỗi chạy quá thời gian trong c++

Đề https://codeforces.com/group/FLVn1Sc504/contest/274766/problem/A
Em lỗi hết 20 test case vì chạy quá thời gian.
Đây lần đầu tiên em gặp lỗi này, em không biết vì sao lại chạy quá thời gian ạ? Mọi người chỉ em cách chỉnh code sao cho hợp lý đc k ạ. Em cảm ơn :sunny:

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
using namespace std; 
void nhapmang (int a[100], int b[100], int sl) { 
   for (int i =0; i<sl;i++) { 
    cin >> a[i]; 
    cin >> b[i]; 
   }
}
int main () { 
   int a[100]; 
   int b[100]; 
   int viec;  
   cin >> viec;
   int n = viec*2; 
   int dem = viec; 
   nhapmang (a,b,n);  
   int tong = 0; 
   bool s[100];
   int c[100]; 
   for (int i = 0 ; i < n;i++) {  
       c[i] = b[i]; 
   }
   set <int> d;
   sort (c,c+n);
   for (int i = 0 ; i < n;i++) { 
       d.insert (c[i]); 
   } 
   vector <int> e (d.begin(), d.end()); 
   int m = 0; 

   for (int i = 0 ; i < n;i++) { 
      if (b[i] < a[i]&&b[i]==e[m]) {
      	  i++; 
      	  m++; 
      	  if (dem==0) break; 
	      if (dem!=0) {
	       s[i] = true; 
          dem--; 
          tong += b[i];  
      } 
	  }
   } 
   for (int i = 0; i < n;i++) { 
       if (!s[i]) { 
           tong += a[i]; 
	   }
   } 
   cout << tong; 
   return 0; 
}

Em cho thêm thông tin đi. Ít thông tin ai muốn giúp cũng không giúp được.
Quá là quá thế nào, hết bao nhiêu giây.
Bất thường ở bước nào ? Khi đang nhập hay đang tính toán.

1 Like

Chạy quá thời gian không phải là lỗi.

Bạn hãy thử đánh giá xem độ phức tạp của code bạn là bao nhiêu.

4 Likes

Có cảm giác là bạn code quá hời hợt đi, đề bài cho n \le 4.10^5 mà trong code chỉ có mảng 100 phần tử…

Mình cũng thấy lạ là lại bị lỗi LTE chứ hổng phải SEGFAULT

4 Likes

Dạ em chạy nguyên code hết 1.59 s ạ. Còn bất thường là sao ạ?

Vâng em hơi ẩu :sweat_smile:

Em nhìn code của em, em thấy nó hơi loằn ngoằn nhưng không bt sửa sao nữa ạ

image

Cho em hỏi sao em nâng mảng lên 10^6 phần tử thì nó không cho nhập ạ ???

Dùng các hàm đo thời gian, sau mỗi lệnh hoặc cụm lệnh (for,while) hiển thị thời gian đã trôi qua để khoanh vùng khu vực chạy chậm đi em.
Ví dụ trên windows có GetTickCount;
Hoặc mấy thư viện có chức năng đó.

10^6 phần tử phải dùng cấp phát động.

5 Likes

Đó cũng là bài học cho bạn đó, không phải ngẫu nhiên mà CP style hay dùng biến mảng toàn cục đâu bạn.

Hơn nữa, đã #include <vector> rồi thì tại sao lại không dùng?

4 Likes

Bài này cho bạn dùng đến 1024 MB = 1GB bộ nhớ để làm. Tức là bạn nên chú trọng vào số lượng phần tử của mảng.
Bài cho n <= 4*10^5, nhưng số lượng bài tập lại là 2n, tức là bạn cần 1 mảng tối đa là 8*10^5 phần tử, còn nữa là 2 mảng cho Tí và Tèo. Trong khi đó, bài bạn làm chỉ khai báo chỉ 100 phần tử cho mỗi mảng.

Nhập 8*10^5 phần tử vào mảng chỉ có 100 phần tử. :thinking:

Dùng nhiều bộ nhớ để giảm thời gian thực thi.

3 Likes

bài này khá gắt, mình viết c++ chỉ dùng vector sort + O(n) mà vẫn tạch

3 Likes

Tuy mình không dành được 100% số điểm, nhưng có thể gợi ý cho bạn thể này

  1. sort theo chiều giảm dần [chênh lệch thời gian giải bài toán i của 2 thành viên kia], nếu bằng thì sort theo min của thời gian giải bài toán của cả 2 người. Nghe có vẻ khó hiểu nên dùng sql diễn tả cho dễ:
  • order by abs(a[i] - b[i]) desc, min(a[i], b[i]) asc
  1. lần lượt xét 2n bài toán (bước 2 này chỉ chạy O[n])
    2.1 nếu một trong hai người đã giải đủ n bài, thì bài toán đang xét sẽ phải giao cho người còn lại
    2.2 nếu cả 2 đều chưa giải đủ n bài, thì chọn người có thời gian giải thấp hơn để giải bài đó

Với cách giải này mình dùng kểu vector<vector> , dùng thư viện algorithm để sort vector đó
Ban đầu được 10/21 (45 points)
Sau đó mình xem lại thì thấy thao tác eraser và pop_back có thể là nguyên nhân (vì nó không hẳn là O(1)) nên đã bỏ đi thì được 15/21 (70 points)

chắc rảnh sẽ tự viết quicksort cho bài này để submit lại :smiley:

5 Likes

Xin lỗi mấy anh do vài tuần qua một số lý do nên giờ em mới rep ạ

Dùng nhiều bộ nhớ để giảm thực thi chương trình là sao vậy ạ, cái này em rất hóng đc nghe

Chi tiết quá, em cảm ơn nhiều ạ :sunny:

Vâng em cảm ơn, học mấy tháng giờ em mới bt, em tìm hiểu rồi ạ :smiley:

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