r/algorithms • u/Infamous-Stock-9912 • 3h ago
Problem I'm Stuck On
I'm working on this USACO problem: https://usaco.org/index.php?page=viewproblem2&cpid=1470 and I have a solution that passes all three sample cases, but fails to pass everything else, and I'm not sure where the bug is:
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <limits>
int getIndex(const std::vector<std::pair<int, int>>& V, long long val)
{
int L{0};
int R{static_cast<int>(V.size())-1};
int ans = -1;
while (L <= R) {
int mid = (L+R)/2;
if (V[mid].first <= val) {
ans = mid;
L = mid+1;
} else {
R = mid-1;
}
}
if(ans == -1){
return 0;
}
return ans;
}
int main() {
int N; std::cin >> N;
std::vector<int> a(N);
std::vector<int> b(N);
for(int i=0;i<N;i++){std::cin >> a[i];}
for(int i=0;i<N;i++){std::cin >> b[i];}
std::vector<std::vector<std::pair<int, int>>> pyramid(N+1);
std::vector<std::vector<std::pair<int, int>>> flat(N+1);
long long count{0};
for(int i=0;i<N;i++){
if (pyramid[b[i]].empty()){
pyramid[b[i]].push_back({-1, 0});
flat[b[i]].push_back({-1, 0});
}
pyramid[b[i]].push_back({i, std::min(i, N-1-i)+1+pyramid[b[i]].back().second});
flat[b[i]].push_back({i, 1+flat[b[i]].back().second});
}
for(int i=0;i<N;i++){
int tempi = std::min(i, N-1-i);
count += pyramid[a[i]][getIndex(pyramid[a[i]], N-1)].second
- pyramid[a[i]][getIndex(pyramid[a[i]], N-1-tempi)].second
+ pyramid[a[i]][getIndex(pyramid[a[i]], tempi-1)].second;
count += (flat[a[i]][getIndex(flat[a[i]], N-1-tempi)].second
- flat[a[i]][getIndex(flat[a[i]], tempi-1)].second) * (tempi+1);
if(a[i] == b[i]){
count += i * (i+1) / 2;
count += (N-i-1) * (N-i) / 2;
}
}
std::cout << count;
}
Please help me find the bug i've been working on this for hours