Robot Instructions

典型的meet in the middle的解法，把所有instructions分成两半，分别生成所有子集，加起来看哪些子集能够到达目的地。

这个题的计算时间比较紧张，直接把所有子集排序后做二分查找匹配会有一个测试点TLE（第5个）。下面的代码用了一个优化，就是把生成的子集中同样的情况合并（merge()将同样情况的数量存在E.cnt中）。

官方题解(英文)用了另外一个优化，就是用双指针（左侧和右侧各一个指针），这样在合并结果的时候节省掉binary search。也有网上解答说unordered_map 也是可以过的。

另外记得要long long，否则最后一个测试点不过。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n;
int xg, yg;
int x[45], y[45];
struct E {
    int x,y,k,cnt;
    bool operator==(const E &b) const {
        return x == b.x && y == b.y && k == b.k && cnt == b.cnt;
    }
    bool operator<(const E &b) const {
        if (x != b.x) return x < b.x;
        if (y != b.y) return y < b.y;
        if (k != b.k) return k < b.k;
        return cnt < b.cnt;
    }
};
vector<E> ml, mr;
ll ans[45];
 
void generate(int l, int r, vector<E> &m) {
    for (int bm = 0; bm < (1 << (r-l+1)); bm++) {
        int dx = 0, dy = 0;
        int ones = 0;
        for (int i = 0; i <= r-l; i++)
            if (bm & (1 << i)) {
                dx += x[l+i];
                dy += y[l+i];
                ones++;
            }
        m.push_back({dx,dy,ones,1});
    }
}
 
void merge(vector<E> &m) {
    vector<E> m2;
    int j = 0;
    int cnt = 1;
    for (int i = 1; i < m.size(); i++) {
        if (m[i].x == m[j].x && m[i].y == m[j].y && m[i].k == m[j].k)
            cnt++;
        else {
            m2.push_back({m[j].x, m[j].y, m[j].k, cnt});
            j = i; cnt = 1;
        }
    }
    m2.push_back({m[j].x, m[j].y, m[j].k, cnt});
    m = m2;
}
 
int main() {
    scanf("%d %d %d", &n, &xg, &yg);
    for (int i = 0; i < n; i++)
        scanf("%d %d", &x[i], &y[i]);
    generate(0, n/2-1, ml);
    generate(n/2, n-1, mr);
    sort(ml.begin(), ml.end());
    sort(mr.begin(), mr.end());
    merge(ml);  // merge cnt of same {x,y,k}
    merge(mr);
 
    for (auto e: ml) {
        int x1 = e.x, y1 = e.y, k1 = e.k;
        E t = {xg-x1,yg-y1,0,0};
        auto it = lower_bound(mr.begin(), mr.end(), t);
        for (; it != mr.end() && it->x == t.x && it->y == t.y; it++)
            ans[k1 + it->k] += (ll)e.cnt * it->cnt;
    }
    for (int k = 1; k <= n; k++)
        printf("%lld\n", ans[k]);
    return 0;
}