Submission #718698

#	Time	Username	Problem	Language	Result	Execution time	Memory
718698		nihaddhuseynli	Robots (IOI13_robots)	C++14	100 / 100	2401 ms	40452 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int check[1000001],ar1[1000001],ar2[1000001];
int t,n1,n2;
struct toy {
    int w1, w2;
    int id;
};
toy toys1[1000001],toys2[1000001];
bool cmp1(toy a, toy b) {
    return a.w1 < b.w1 || (a.w1 == b.w1 && a.w2 < b.w2);
}
bool cmp2(toy a, toy b) {
    return a.w2 < b.w2 || (a.w2 == b.w2 && a.w1 < b.w1);
}
ll func(ll x)
{
    ll rem = t;
    priority_queue<pair<int,int>> pq;
    int ind = 0;
    for (int i = 0; i < n1; i++) {
        while (ind != t && (check[toys1[ind].id] || toys1[ind].w1 < ar1[i])) {
            if (!check[toys1[ind].id])
                pq.push({ toys1[ind].w2, toys1[ind].id });
            ind++;
        }
        int tt = x;
        while (!pq.empty() && tt--) {
            int cur = pq.top().second;
            pq.pop();
            rem--;
            check[cur] = true;
        }
    }
    pq = priority_queue<pair<int,int>>();
    ind = 0;
    for (int i = 0; i < n2; i++) {
        while (ind != t && (check[toys2[ind].id] || toys2[ind].w2 < ar2[i])) {
            if (!check[toys2[ind].id])
                pq.push({ toys2[ind].w1, toys2[ind].id });
            ind++;
        }
        int tt = x;
        while (!pq.empty() && tt--) {
            int cur = pq.top().second;
            pq.pop();
            check[cur] = true;
            rem--;
        }
    }
    return rem == 0;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    n1=A;
    n2=B;
    t=T;
    for(int i =0;i<n1;i++)
    {
        ar1[i]=X[i];
    }
    for(int i =0;i<n2;i++)
    {
        ar2[i]=Y[i];
    }
    for(int i =0;i<T;i++)
    {
        toys1[i]=toys2[i]={W[i],S[i],i};
    }
    sort(toys1,toys1+T,cmp1);
    sort(toys2,toys2+T,cmp2);
    if(A)
    {
        sort(ar1,ar1+n1);
    }
    if(B)
    {
        sort(ar2,ar2+n2);
    }
    int l =0,r=T;
    while(l<r)
    {
        ll mid=l+(r-l)/2;
        if(func(mid))
        {
            r=mid;
        }
        else
        {
            l=mid+1;
        }
        memset(check,0,sizeof(check));
    }
    return func(l) ? l : -1;
}

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