제출 #237925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
237925		nicolaalexandra	로봇 (IOI13_robots)	C++14	90 / 100	3086 ms	25336 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,s2;
int a[DIM],b[DIM];

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

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

    return 1;
}

int try_robot_weight (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;
    s.clear(), s2.clear();
    for (i=1;i<=a[0];i++)
        s.insert(make_pair(a[i],val));
    for (i=1;i<=b[0];i++)
        s2.insert(make_pair(b[i],val));

    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)
            ok |= try_robot_weight(v[i].first);

        if (!ok)
            return 0;
    }
    return 1;
}

int putaway (int nr, int nr2, int n, int A[], int B[], int Weight[], int Size[]){
    int i;
    for (i=0;i<n;i++)
        v[i+1] = make_pair(Weight[i],Size[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);
    }

    for (i=1;i<=n;i++){
        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