0

这就是谷歌代码堵塞的商店信用问题。 https://code.google.com/codejam/contest/351101/dashboard#s=p0

我的代码在运行大型测试后给出了一个 SIGSEGV。但答案是正确的！

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int ps[1000]={0};
vector<int> indice[1000];
int main() {
  int cases; scanf("%d", &cases);
  for(int j=1;j<=cases;j++) {
    printf("Case #%d: ", j);
    int c, is; scanf("%d%d", &c, &is);
    for(int i=0;i<=c;i++) ps[i]=0;
    for(int i=0;i<=c;i++) indice[i].clear();
    for (int i = 0; i < is; i++) {
      int it; scanf("%d", &it);
      indice[it].push_back(i+1);
      ps[it]=1;
      if (c-it>0&&ps[c-it]) {
        int a, b;
        a = indice[it][0];
        b = indice[c-it][0];
        if(c==2*it&&indice[it].size()>1) {
          b=indice[it][1];
        }

        if (a!=b) {
          printf("%d %d\n", min(a,b),max(a,b));
        }
      }
    }
  }
  return 0;
}

所以我使用 valgrind 来找出发生了什么.. 但似乎这不是我的问题。

==17599== Invalid free() / delete / delete[] / realloc()
==17599==    at 0x4C2A4BC: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==17599==    by 0x401669: __gnu_cxx::new_allocator<int>::deallocate(int*, unsigned long) (new_allocator.h:98)
==17599==    by 0x4013CD: std::_Vector_base<int, std::allocator<int> >::_M_deallocate(int*, unsigned long) (stl_vector.h:156)
==17599==    by 0x400F60: std::_Vector_base<int, std::allocator<int> >::~_Vector_base() (stl_vector.h:142)
==17599==    by 0x400D8D: std::vector<int, std::allocator<int> >::~vector() (stl_vector.h:351)
==17599==    by 0x400C48: __tcf_0 (a.cpp:6)
==17599==    by 0x5383900: __run_exit_handlers (exit.c:78)
==17599==    by 0x5383984: exit (exit.c:100)
==17599==    by 0x5369773: (below main) (libc-start.c:258)
==17599==  Address 0x1 is not stack'd, malloc'd or (recently) free'd
==17599== 
==17599== 
==17599== HEAP SUMMARY:
==17599==     in use at exit: 128 bytes in 1 blocks
==17599==   total heap usage: 4,527 allocs, 4,527 frees, 113,664 bytes allocated
==17599== 
==17599== LEAK SUMMARY:
==17599==    definitely lost: 0 bytes in 0 blocks
==17599==    indirectly lost: 0 bytes in 0 blocks
==17599==      possibly lost: 0 bytes in 0 blocks
==17599==    still reachable: 128 bytes in 1 blocks
==17599==         suppressed: 0 bytes in 0 blocks
==17599== Rerun with --leak-check=full to see details of leaked memory
==17599== 
==17599== For counts of detected and suppressed errors, rerun with: -v
==17599== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 2 from 2)

我很困惑......谁能告诉我发生了什么事？我是 C++ 的新手 .. 非常感谢。

4

1 回答 1

2

据我了解 valgrind，它无法检测到您正在编写超出静态分配的数组范围的内容。所以让我们在堆上分配它们。

vector<int> *indice = new vector<int>[1000];
int *ps = new int[1000];

然后，您会看到 valgrind 出现错误。包含：

==7168== Invalid read of size 8
==7168==    at 0x4008D6: main (stl_vector.h:735)
==7168==  Address 0x4c39e10 is 8 bytes after a block of size 24,008 alloc'd
==7168==    at 0x4A07152: operator new[](unsigned long) (vg_replace_malloc.c:363)
==7168==    by 0x400791: global constructors keyed to indice (foo.cc:6)
==7168==    by 0x400C35: ??? (in /tmp/foo)
==7168==    by 0x4005F2: ??? (in /tmp/foo)
==7168== 
==7168== Invalid read of size 8
==7168==    at 0x4008DA: main (stl_vector.h:735)
==7168==  Address 0x4c39e18 is 16 bytes after a block of size 24,008 alloc'd
==7168==    at 0x4A07152: operator new[](unsigned long) (vg_replace_malloc.c:363)
==7168==    by 0x400791: global constructors keyed to indice (foo.cc:6)
==7168==    by 0x400C35: ??? (in /tmp/foo)
==7168==    by 0x4005F2: ??? (in /tmp/foo)
==7168==

并且使用 gdb，我可以看到 SIGSEGV 在您访问时发生indice[1433]，这超出了indice.

我还认为您的实际问题是对于大型数据集，变量边界列为：

N = 50
3 ≤ I ≤ 2000

你确定你不应该分配 2001 个元素，而不是 1000 个？

于 2013-04-12T03:14:30.220 回答