Submission #237927

#	Time	Username	Problem	Language	Result	Execution time	Memory
237927		nicolaalexandra	Robots (IOI13_robots)	C++14	90 / 100	3082 ms	23544 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
#define DIM 1000010
using namespace std;

pair <int,int> v[DIM];
multiset <pair<int,int> > s;
int a[DIM],b[DIM],f[DIM];

int try_robot_size (int val){
    multiset <pair<int,int> > :: iterator it = s.lower_bound(make_pair(val,0));
    if (it == s.end() || it->first < val)
        return 0;

    int nr = it->first, cnt = it->second;
    s.erase(it);
    cnt--;
    if (cnt)
        s.insert(make_pair(nr,cnt));

    return 1;
}

int verif (int val, int n){
    int i;

    for (i=1;i<=a[0];++i)
        f[i] = 0;

    s.clear();
    for (i=1;i<=b[0];++i)
        s.insert(make_pair(b[i],val));

    int k = a[0];

    for (i=n;i;--i){
        /// incerc sa cuplez jucaria asta cu un robot de marime
        int ok = try_robot_size(v[i].second);
        if (!ok){
            int nr = v[i].first;

            if (k <= 0 || a[k] < nr)
                return 0;

            f[k]++;
            if (f[k] == val)
                k--;
        }
    }
    return 1;
}

int putaway (int nr, int nr2, int n, int A[], int B[], int Weight[], int Size[]){
    int i;

    int max_weight = 0, max_size = 0;
    a[0] = nr;
    for (i=0;i<nr;++i){
        a[i+1] = A[i] - 1;
        max_weight = max (max_weight,A[i]-1);
    }
    b[0] = nr2;
    for (i=0;i<nr2;++i){
        b[i+1] = B[i] - 1;
        max_size = max (max_size,B[i]-1);
    }
    sort (a+1,a+nr+1);

    for (i=1;i<=n;++i){
        v[i] = make_pair (Weight[i-1],Size[i-1]);
        if (v[i].first > max_weight && v[i].second > max_size)
            return -1;
    }

    sort (v+1,v+n+1);

    int st = 1, dr = n, sol = n;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (verif(mid,n)){
            sol = mid;
            dr = mid-1;
        } else st = mid+1;
    }

    return sol;

}

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