双向搜索双指针tle求调
查看原帖
双向搜索双指针tle求调
1229988
Justin_love_coding楼主2024/5/28 07:26

#5 #16 tle

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using PII = pair<int, int>;
const int N = 1000010;
int opx[50], opy[50], ans[50];
vector< pair<PII, int> > l, r, cur;
int main()
{
    int n;
    cin >> n;
    int xg, yg;
    cin >> xg >> yg;
    for (int i = 1; i <= n; i ++ )
        cin >> opx[i] >> opy[i];

    int mid = n >> 1;
    l.push_back({{0, 0}, 0});
    for (int i = 1; i <= mid; i ++ )
    {
        cur.clear();
        for (auto x : l)
            cur.push_back({{x.first.first + opx[i], x.first.second + opy[i]}, x.second + 1});
        for (auto x : cur)
            l.push_back(x);
    }
    sort(l.begin(), l.end());

    r.push_back({{xg, yg}, 0});
    for (int i = mid + 1; i <= n; i ++ )
    {
        cur.clear();
        for (auto x : r)
            cur.push_back({{x.first.first - opx[i], x.first.second - opy[i]}, x.second + 1});
        for (auto x : cur)
            r.push_back(x);
    }
    sort(r.begin(), r.end());

    for (int i = 0, j = 0; i < l.size(); i ++ )
    {
        while (l[i].first > r[j].first && j < r.size() - 1) j ++ ;
        if (l[i].first == r[j].first)
        {
            int k = j;
            while (l[i].first == r[j].first) ans[l[i].second + r[j ++ ].second] ++ ;
            j = k;
        }
    }
    for (int i = 1; i <= n; i ++ )
        cout << ans[i] << endl;
    return 0;
}
2024/5/28 07:26
加载中...