2021中国大学生程序设计竞赛（CCPC）- 网络选拔赛（重赛）Monopoly

    #include<bits/stdc++.h>
    #include <unordered_map>
    using namespace std;
    template<class...Args>
    void debug(Args... args) {//Parameter pack
    auto tmp = { (cout << args << ' ', 0)... };
    cout << "\n";
    }
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<ll, ll>pll;
    typedef pair<int, int>pii;
    const ll N = 5e5 + 5;
    const ll INF = 0x7fffffff;
    const ll MOD = 998244353;
    
    ll sum[N];
    set<ll>bucket[N];//桶(存放模数相同的数的集合)
    map<ll, ll>_hash;//模数转化为桶的位置(离散化)
    map<ll, ll>_pos;//值转换为位置(保存最强面的位置即可)
    void init() {
    for (auto it = _hash.begin(); it != _hash.end(); it++)bucket[it->second].clear();
    memset(sum, 0, sizeof sum);
    _hash.clear();
    _pos.clear();
    }
    int main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        init();
        int n, m;
        cin >> n >> m;
        ll S = 0;
        for (int i = 1; i <= n; i++) {
            cin >> sum[i];
            S += sum[i];
            sum[i] += sum[i - 1];//前缀和
            if (_pos.count(sum[i]) == 0) _pos[sum[i]] = i;//存下数对应的地址
        }
        if (S != 0) {
            ll cnt = 0;
            for (int i = 1; i <= n; i++) {
                ll tt = ((sum[i] % S) + S) % S;
                if (_hash[tt] == 0) _hash[tt] = ++cnt;//离散化
                bucket[_hash[tt]].insert(sum[i]);//存入对应的集合中去
            }
            while (m--) {
                ll x;
                cin >> x;
                ll tt = ((x % S) + S) % S;
                if (x == 0) cout << 0 << "\n";
                else if (bucket[_hash[tt]].size() == 0) cout << -1 << "\n";
                else {
                    if (S > 0) {
                        set<ll>::iterator it = bucket[_hash[tt]].upper_bound(x);
                        if (it == bucket[_hash[tt]].begin())cout << -1 << "\n";
                        else {
                            it--;
                            cout << (x - *it) / S * n + _pos[*it] << "\n";
                        }
                    }
                    else {
                        set<ll>::iterator it = bucket[_hash[tt]].lower_bound(x);
                        if (it == bucket[_hash[tt]].end())cout << -1 << "\n";
                        else {
                            cout << (x - *it) / S * n + _pos[*it] << "\n";
                        }
                    }
                }
            }
        }
        else {
            while (m--) {
                int x;
                cin >> x;
                if (x == 0)cout << 0 << "\n";
                else {
                    if (_pos[x] == 0)cout << -1 << "\n";
                    else cout << _pos[x] << "\n";
                }
            }
        }
    }
    return 0;
    }