Submission #787825

#	Time	Username	Problem	Language	Result	Execution time	Memory
787825		drdilyor	Robots (IOI13_robots)	C++17	28 / 100	1597 ms	18432 KiB

robots

#include "robots.h"
#include <algorithm>
#include <cstring>
#include <functional>
#include <iostream>
#include <cassert>
#include <numeric>
#include <queue>
using namespace std;
struct Fenwick {
    int n;
    vector<int> tree;

    Fenwick(int n) : n(n) {
        tree.assign(n, 0);
    }

    void inc(int pos, int val) {
        for (; pos < n; pos |= (pos + 1)) {
            tree[pos] += val;
        }
    }

    int sum(int r) { // [0, r]
        int ans = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1) {
            ans += tree[r];
        }
        return ans;
    }

    int sum(int l, int r) { // [l, r]
        return sum(r) - sum(l - 1);
    }
};

struct fset {
    int n;
    Fenwick fw;
    fset(int n) : fw(n) {}
};

int putaway(int wrobot, int srobot, int n, int rw[], int rs[], int w[], int s[]) {

    sort(rw, rw + wrobot);
    sort(rs, rs + srobot);


    //{
    //    vector<pair<int,int>> cpw;
    //    for (int i = 0; i < n;i++) {
    //        cpw.emplace_back(w[i], i);
    //    }
    //    for (int i = 0; i < wrobot; i++) {
    //        cpw.emplace_back(rw[i], ~i);
    //    }
    //    sort(cpw.begin(), cpw.end());
    //    for (int k = 0; k < (int) cpw.size(); k++) {
    //        int i = cpw[k].second;
    //        if (i >= 0) w[i] = k;
    //        else rw[~i] = k;
    //    }
    //}
    //{
    //    vector<pair<int,int>> cps;
    //    for (int i = 0; i < n;i++) {
    //        cps.emplace_back(s[i], i);
    //    }
    //    for (int i = 0; i < srobot; i++) {
    //        cps.emplace_back(rs[i], ~i);
    //    }
    //    sort(cps.begin(), cps.end());
    //    for (int k = 0; k < (int) cps.size(); k++) {
    //        int i = cps[k].second;
    //        if (i >= 0) s[i] = k;
    //        else rs[~i] = k;
    //    }
    //}

    auto comp_w = [&](int i, int j)->bool{ return w[i] < w[j]; };
    auto comp_s = [&](int i, int j)->bool{ return s[i] < s[j]; };
    int* byw = new int[n];
    int* bys = new int[n];
    iota(byw, byw + n, 0);
    iota(bys, bys + n, 0);
    sort(byw, byw + n, comp_w);
    sort(bys, bys + n, comp_s);

    int* done = new int[n];

    auto check = [&](int time)->bool {
        cerr << time << '\n';
        if ((int64_t)time * (wrobot + srobot) < n) return false;
        memset(done, 0, sizeof(*done)*n);

        {
            int toy = 0;
            priority_queue<pair<int,int>> st;

            for (int rob = 0; rob < wrobot; rob++) {
                while (toy < n && w[byw[toy]] < rw[rob]) {
                    st.push({-s[byw[toy]], byw[toy]});
                    toy++;
                }
                for (int rem = 0; rem < time && st.size(); rem++) {
                    done[st.top().second] = 1;
                    st.pop();
                }
            }
        }

        {
            int toy = 0;
            priority_queue<pair<int,int>> st;

            for (int rob = 0; rob < srobot; rob++) {
                while (toy < n && s[bys[toy]] < rs[rob]) {
                    if (!done[bys[toy]])
                        st.push({-w[bys[toy]], bys[toy]});
                    toy++;
                }
                for (int rem = 0; rem < time && st.size(); rem++) {
                    done[st.top().second] = 1;
                    st.pop();
                }
            }
        }
        int all_done = accumulate(done, done + n, 1, bit_and<>());
        return all_done;
    };

    int l = -1, r = n +1;
    while (l < r - 1) {
        int mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return r == n+1 ? -1 : r;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10