Submission #1087998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087998		MateiKing80	Robots (IOI13_robots)	C++14	0 / 100	1 ms	600 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
//#define int ll

using pii = pair<int, int>;
#define fr first
#define sc second


struct AIB
{
    vector<int> aib;
    int n;

    inline int lsb(int x)
    {
        return x & -x;
    }

    AIB(int N, int k)
    {
        n = N;
        aib.resize(n + 1);
        for(int i = 1; i <= n; i ++)
            aib[i] = lsb(i) * k;
    }

    void upd(int pos)
    {
        while(pos <= n)
            aib[pos] --, pos += lsb(pos);
    }

    int query(int pos)
    {
        int ans = 0;
        while(pos)
        {
            ans += aib[pos];
            pos -= lsb(pos);
        }
        return ans;
    }

    int binara(int val)
    {
        int pas = (1 << 20), pos = 0, ans = 0;
        while(pas)
        {
            if(pos + pas <= n && aib[pos + pas] + ans < val)
                pos += pas, ans += aib[pos];
            pas /= 2;
        }
        return pos + 1;
    }
};

bool doable(int a, int b, int t, vector<pii> r)
{
    AIB ds(a, t);
    vector<pii> baga;
    for(auto i : r)
    {
        baga.push_back(i);
        if(i.fr == -1)
            continue;
        int p = ds.query(i.fr + 1);
        if(p == 0)
            continue;
        baga.pop_back();
        ds.upd(ds.binara(p));
    }
    AIB ds2(b, t);
    for(auto i : baga)
    {
        if(i.sc == -1)
            return false;
        int p = ds2.query(i.sc + 1);
        if(p == 0)
            return false;
        ds2.upd(ds2.binara(p));
    }
    return true;
}

signed putaway(signed a, signed b, signed t, signed x[], signed y[], signed w[], signed s[])
{
    sort(x, x + a, greater<int>());
    sort(y, y + b, greater<int>());
    vector<pii> r;
    for(int i = 0; i < t; i ++)
    {
        int pas = (1 << 20), pos = -1;
        while(pas)
        {
            if(pos + pas < a && x[pos + pas] >= w[i])
                pos += pas;
            pas /= 2;
        }
        r.push_back({pos, 0});
        pas = (1 << 20), pos = -1;
        while(pas)
        {
            if(pos + pas < b && y[pos + pas] >= s[i])
                pos += pas;
            pas /= 2;
        }
        r.back().sc = pos;
        if(r.back() == make_pair(-1, -1))
            return -1;
    }
    sort(r.begin(), r.end(), [&](pii a, pii b){return a.sc < b.sc;});
    int pas = (1 << 20), pos = 0;
    while(pas)
    {
        if(!doable(a, b, pos + pas, r))
            pos += pas;
        pas /= 2;
    }
    return pos + 1;
}
/*
signed main()
{
    int a, b, t, x[50005], y[50005], w[50005], s[50005];
    cin >> a >> b >> t;
    for(int i = 0; i < a; i ++)
        cin >> x[i];
    for(int i = 0; i < b; i ++)
        cin >> y[i];
    for(int i = 0; i < t; i ++)
        cin >> w[i];
    for(int i = 0; i < t; i ++)
        cin >> s[i];
    cout << putaway(a, b, t, x, y, w, s);
}*/
/*
3
2
10
6 2 9
4 7
4 8 2 7 1 5 3 8 7 10
6 5 3 9 8 1 3 7 6 5
*/

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