题目:
CF1690E Price Maximization
代码:
Probably, the solution is executed with error 'out of bounds' on the line 38
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll T, n, k, a[200010];
vector<ll> f[1010];
int main(){
cin >> T;
while(T--){
scanf("%lld %lld", &n, &k);
for(ll i = 0; i < k; i++) f[i].clear();
for(ll i = 1; i <= n; i++){
scanf("%lld", &a[i]); f[a[i] % k].push_back(a[i]);
}
ll ans = 0;
for(ll i = 0; i < k; i++){
if(!f[i].size()) continue;
if(i == 0){
ll t = f[i].size();
for(ll j = 1; j <= t / 2; j++){
ll t1 = f[i][f[i].size() - 1], t2 = f[i][f[i].size() - 2];
ans += (t1 + t2) / k;
f[i].pop_back(); f[i].pop_back();
}
}else{
ll t = min(f[i].size(), f[k - i].size());
for(ll j = 1; j <= t; j++){
ll t1 = f[i][f[i].size() - 1], t2 = f[k - i][f[k - i].size() - 1];
ans += (t1 + t2) / k;
f[i].pop_back(); f[k - i].pop_back();
}
}
}
ll last = -1;
for(ll i = 0; i < k; i++)
if(f[i].size()){
ll t = f[i].size();
for(ll tmp = 0; tmp < t; tmp++){
ll j = f[i][tmp]; //这是报错的地方(行)
if(last == -1) last = j;
else{
ans += (last + j) / k; last = -1;
}
if(f[i].size() > 1) f[i].pop_back();
}
}
printf("%lld\n", ans);
}
return 0;
}
CF 报错:
Diagnostics detected issues [cpp.clang++-diagnose]: =================================================================
==4560==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x13200198 at pc 0x00ab434e bp 0x1124ec14 sp 0x1124ec10
READ of size 8 at 0x13200198 thread T0
==4560==WARNING: Failed to use and restart external symbolizer!
#0 0xab434d in main K:\codeforces71\f1c52866cb1978b34ee994e89371cee3\compile-06b338c55c3ccce0450200b1db48e07b\p71.cpp:38
#1 0xb2d6f1 in __scrt_common_main_seh f:\dd\vctools\crt\vcstartup\src\startup\exe_common.inl:283
#2 0x769467f8 in BaseThreadInitThunk+0x18 (C:\Windows\System32\KERNEL32.DLL+0x6b8167f8)
#3 0x778a7f4c in RtlGetFullPathName_UEx+0xac (C:\Windows\SYSTEM32\ntdll.dll+0x4b2e7f4c)
#4 0x778a7f1a in RtlGetFullPathName_UEx+0x7a (C:\Windows\SYSTEM32\ntdll.dll+0x4b2e7f1a)
0x13200198 is located 0 bytes to the right of 8-byte region [0x13200190,0x13200198)
allocated by thread T0 here:
#0 0xb2bc77 in operator new C:\src\llvm_package_1201-final\llvm-project\compiler-rt\lib\asan\asan_new_delete.cpp:99
#1 0xad6aad in std::_Default_allocate_traits::_Allocate C:\Program Files (x86)\Microsoft Visual Studio\2017\Enterprise\VC\Tools\MSVC\14.14.26428\include\xmemory0:52
#2 0xad68e7 in std::_Allocate<8,std::_Default_allocate_traits,0> C:\Program Files (x86)\Microsoft Visual Studio\2017\Enterprise\VC\Tools\MSVC\14.14.26428\include\xmemory0:201
#3 0xaefafc in std::allocator<long long>::allocate C:\Program Files (x86)\Microsoft Visual Studio\2017\Enterprise\VC\Tools\MSVC\14.14.26428\include\xmemory0:1036
#4 0xaeeac4 in std::vector<long long,std::allocator<long long> >::_Emplace_reallocate<const long long &> C:\Program Files (x86)\Microsoft Visual Studio\2017\Enterprise\VC\Tools\MSVC\14.14.26428\include\vector:1005
#5 0xaee16d in std::vector<long long,std::allocator<long long> >::emplace_back<const long long &> C:\Program Files (x86)\Microsoft Visual Studio\2017\Enterprise\VC\Tools\MSVC\14.14.26428\include\vector:971
#6 0xab613b in std::vector<long long,std::allocator<long long> >::push_back C:\Program Files (x86)\Microsoft Visual Studio\2017\Enterprise\VC\Tools\MSVC\14.14.26428\include\vector:981
#7 0xab209d in main K:\codeforces71\f1c52866cb1978b34ee994e89371cee3\compile-06b338c55c3ccce0450200b1db48e07b\p71.cpp:12
#8 0xb2d6f1 in __scrt_common_main_seh f:\dd\vctools\crt\vcstartup\src\startup\exe_common.inl:283
#9 0x769467f8 in BaseThreadInitThunk+0x18 (C:\Windows\System32\KERNEL32.DLL+0x6b8167f8)
#10 0x778a7f4c in RtlGetFullPathName_UEx+0xac (C:\Windows\SYSTEM32\ntdll.dll+0x4b2e7f4c)
#11 0x778a7f1a in RtlGetFullPathName_UEx+0x7a (C:\Windows\SYSTEM32\ntdll.dll+0x4b2e7f1a)
SUMMARY: AddressSanitizer: heap-buffer-overflow K:\codeforces71\f1c52866cb1978b34ee994e89371cee3\compile-06b338c55c3ccce0450200b1db48e07b\p71.cpp:38 in main
Shadow bytes around the buggy address:
0x3263ffe0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x3263fff0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x32640000: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x32640010: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x32640020: fa fa fa fa fa fa fa fa fa fa 00 fa fa fa 00 fa
=>0x32640030: fa fa 00[fa]fa fa fd fd fa fa 00 00 fa fa fd fd
0x32640040: fa fa fd fa fa fa fd fa fa fa fd fa fa fa 00 fa
0x32640050: fa fa 06 fa fa fa fd fa fa fa 05 fa fa fa 06 fa
0x32640060: fa fa 01 fa fa fa fd fa fa fa fd fa fa fa fd fa
0x32640070: fa fa fd fa fa fa fd fa fa fa 00 fa fa fa fd fa
0x32640080: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
Shadow gap: cc
==4560==ABORTING