Submission #1098664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098664		rahidilbayramli	Robots (IOI13_robots)	C++17	100 / 100	2308 ms	63712 KiB

robots

#include "robots.h"
#pragma GCC optimize("-O3")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define p_b pop_back
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    int i, j;
    if(!B)
    {
        int maxx = 0;
        for(i = 0; i < T; i++)
            maxx = max(maxx, W[i]);
        int mx = 0;
        for(i = 0; i < A; i++)
            mx = max(mx, X[i]);
        if(mx <= maxx)
            return -1;
        vl vect1, vect2;
        for(i = 0; i < T; i++)
            vect1.pb(W[i]);
        vect1.pb(LLONG_MAX);
        sort(all(vect1));
        for(i = 0; i < A; i++)
            vect2.pb(X[i]);
        sort(all(vect2));
        priority_queue<pii>pq;
        i = 0, j = 0;
        vl idx[T+5];
        while(i < (int)(vect2.size()) && j < (int)(vect1.size()-1))
        {
            if(vect2[i] <= vect1[j])
                i++;
            else    if(vect2[i] > vect1[j] && vect2[i] <= vect1[j+1])
            {
                idx[j].pb(vect2[i]);
                i++;
            }
            else
                j++;
        }
        for(i = T - 1; i >= 0; i--)
        {
            for(auto u : idx[i])
                pq.push({0, u});
            ll a = pq.top().f, b = pq.top().s;
            pq.pop();
            a = -a;
            a++;
            pq.push({-a, b});
        }
        maxx = 0;
        while(!pq.empty())
        {
            maxx = max(maxx, -pq.top().f);
            pq.pop();
        }
        return maxx;
    }
    if(!A)
    {
        int maxx = 0;
        for(i = 0; i < T; i++)
            maxx = max(maxx, S[i]);
        int mx = 0;
        for(i = 0; i < B; i++)
            mx = max(mx, Y[i]);
        if(mx <= maxx)
            return -1;
        vl vect1, vect2;
        for(i = 0; i < T; i++)
            vect1.pb(S[i]);
        vect1.pb(LLONG_MAX);
        sort(all(vect1));
        for(i = 0; i < B; i++)
            vect2.pb(Y[i]);
        sort(all(vect2));
        priority_queue<pii>pq;
        i = 0, j = 0;
        vl idx[T+5];
        while(i < (int)(vect2.size()) && j < (int)(vect1.size()-1))
        {
            if(vect2[i] <= vect1[j])
                i++;
            else    if(vect2[i] > vect1[j] && vect2[i] <= vect1[j+1])
            {
                idx[j].pb(vect2[i]);
                i++;
            }
            else
                j++;
        }
        for(i = T - 1; i >= 0; i--)
        {
            for(auto u : idx[i])
                pq.push({0, u});
            ll a = pq.top().f, b = pq.top().s;
            pq.pop();
            a = -a;
            a++;
            pq.push({-a, b});
        }
        maxx = 0;
        while(!pq.empty())
        {
            maxx = max(maxx, -pq.top().f);
            pq.pop();
        }
        return maxx;
    }
    int n = T;
    int w[n+5], s[n+5];
    int a = A, b = B;
    int x[a+5], y[b+5];
    for(i = 1; i <= n; i++)
    {
        w[i] = W[i-1];
        s[i] = S[i-1];
    }
    vl v1;
    for(i = 1; i <= a; i++)
        x[i] = X[i-1];
    for(i = 1; i <= b; i++)
        y[i] = Y[i-1];
    vector<pair<pll, ll>>vect1;
    for(i = 1; i <= n; i++)
        vect1.pb({{s[i], w[i]}, i});
    sort(rall(vect1));
    int l = 1, r = n+1, res = n+1;
    int mp[a+5], mp2[b+5], cnt[n+5];
    while(l <= r){
        int mid = (l + r) / 2, dd = 0;
        set<pii>stt, stt2;
        for(i = 1; i <= n; i++)
            cnt[i] = 0;
        for(i = 1; i <= a; i++){
            stt.insert({x[i], i});
            mp[i] = 0;
        }
        for(i = 1; i <= b; i++){
            stt2.insert({y[i], i});
            mp2[i] = 0;
        }
        stt.insert({INT_MAX, a+1});
        stt2.insert({INT_MAX, b+1});
        for(i = 0; i < vect1.size(); i++)
        {
            auto iter = stt.lower_bound({vect1[i].f.s+1, 0});
            if((*iter).f == INT_MAX)
                continue;
            int idx = (*iter).s;
            mp[idx]++;
            cnt[vect1[i].s]++;
            dd++;
            if(mp[idx] == mid)
                stt.erase(iter);
        }
        vector<pair<pll, ll>>vect;
        for(i = 1; i <= n; i++)
        {
            if(!cnt[i])
                vect.pb({{w[i], s[i]}, i});
        }
        for(i = 0; i < vect.size(); i++)
        {
            auto iter = stt2.lower_bound({vect[i].f.s+1, 0});
            if((*iter).f == INT_MAX)
                continue;
            int idx = (*iter).s;
            mp2[idx]++;
            dd++;
            if(mp2[idx] == mid)
                stt2.erase(iter);
        }
        if(dd == n)
        {
            res = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    if(res == n+1)
        return -1;
    return res;
}
/*int main()
{
    int A, B, T;
    cin >> T >> A >> B;
    int X[A], Y[B], W[T], S[T];
    for(int i = 0; i < T; i++)
        cin >> W[i];
    for(int i = 0; i < T; i++)
        cin >> S[i];
    for(int i = 0; i < A; i++)
        cin >> X[i];
    for(int i = 0; i < B; i++)
        cin >> Y[i];
    cout << putaway(A, B, T, X, Y, W, S) << "\n";
}
*/

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:160:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |         for(i = 0; i < vect1.size(); i++)
      |                    ~~^~~~~~~~~~~~~~
robots.cpp:178:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |         for(i = 0; i < vect.size(); i++)
      |                    ~~^~~~~~~~~~~~~

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