Source Code
#include <bits/stdc++.h>

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds; // pb_ds
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>


using namespace std;
typedef long long ll;
typedef long double ld;
#define EPS (1e-9)

//             N  E  S  W  NW  NE SE SW
//int dr[] = {-1, 0, 1, 0, -1, -1, 1, 1};
//int dc[] = {0, 1, 0, -1, -1, 1, 1, -1};
#define fi first
#define se second

bool canBeUsedHere(const int val, const vector<int> &ans, const int j) {
    int prev = j - 1;
    if (prev >= 0) {
        if (val == ans[prev]) return false;
    }

    int nxt = j + 1;
    if (nxt < ans.size()) {
        if (val == ans[nxt]) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);

    int tt;
    cin >> tt;
    while (tt--) {
        int n, m;
        cin >> n >> m;

        vector<pair<ll, int>> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i].fi;
            a[i].se = i;
        }
        sort(a.begin(), a.end());

        vector<pair<int, pair<ll, int>>> b(m);
        for (int i = 0; i < m; ++i) {
            cin >> b[i].se.fi;
            b[i].se.se = i;
            const pair<ll, int> key(b[i].se.fi + 1, -1);
            const int idx = lower_bound(a.begin(), a.end(), key) - a.begin();
            b[i].fi = n - idx;
        }
        sort(b.begin(), b.end());

        vector<int> ans(m, -1);
        int wins = 0;
        for (int i = m - 1; i >= 0; --i) {
            const pair<ll, int> key(b[i].se.fi + 1, -1);
            int j = lower_bound(a.begin(), a.end(), key) - a.begin();
            j %= n;
            int cnt = 0;
            while (true) {
                ++cnt;
                if (canBeUsedHere(a[j].se, ans, b[i].se.se)) {
                    if (a[j].fi > b[i].se.fi) ++wins;
                    break;
                } else {
                    ++j;
                    j %= n;
                }
                if (cnt > 2 * n) assert(false);
            }
            ans[b[i].se.se] = a[j].se;
        }

        cout << wins << '\n';
        for (int i = 0; i < m; ++i) {
            if (i > 0) cout << ' ';
            cout << ans[i] + 1;
        }
        cout << '\n';
    }

    return 0;
}
Copy
Ayoub vs Mahmoud Omar_Elaraby
GNU G++17
0 ms
644 KB
Runtime Error