Problem Info
Robot Instructions: USACO
My Work
#include <bits/stdc++.h>
using namespace std;
#define int long long
using vi = vector<int>;
using pi = pair<int, int>;
#define pb push_back
#define f first
#define s second
vector<pi> tmp;
int nd, n, rx, ry;//rx is the goal x; ry is the goal y
map<pi, map<int, int>> tot;//tot[i][j] is the number of ways to get pair i with j pairs
vi ret;
void gen(int st, int tx, int ty, int prs){//st is the starting index, tx is the total x value of this subset, ty is the total y value of the subset, prs is the number of pairs in this subset
//if you are looking at the second half of the possible pairs then you want to find the number of ways so that i+(the current subset) = (rx, ry)
if(nd==n){
int c = 0;
for(pi i: tot[{rx-tx, ry-ty}]){
c++;
ret.at(i.f+prs)+=i.s;
}
assert(c<41);//complexity of gen should be at most 40*2^20
}else{
tot[{tx, ty}][prs]++;
}
for(int i = st+1; i<nd; i++){//generate all subsets from st to nd
gen(i, tx+tmp[i].f, ty+tmp[i].s, prs+1);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
//freopen("test.in", "r", stdin);
cin>>n>>rx>>ry;
for(int i = 0; i<n; i++){
int a, b;
cin>>a>>b;
tmp.pb({a, b});
ret.pb(0);
}
ret.pb(0);
nd = n/2;
gen(-1, 0, 0, 0);//generates all subsets with the first n/2 elements
nd = n;
gen(n/2-1, 0, 0, 0);//generates all subsets from the n/2th element to the last element
for(int i =1; i<=n; i++){
cout<<ret[i]<<endl;
}
}
The code splits the array into two separate arrays of equal length and then tests if you can sum up to the resulting pair (rx, ry).
What I’ve Tried
I downloaded the usaco test data and it worked fine for me. I also compared the speed of benq’s offical solution to my local solution and I didn’t notice any difference in execution speed. I use onlinegdb, so I know it isn’t just my computer being fast.
Question
Why is my code running slow on the USACO server? It runs perfectly fine on onlinegdb compiler using usaco’s downloaded data. My assert statement makes sure that the number of times a loop is run is at most 41.
PS: you probably should make it so that people cannot flag their own questions.
