Submission #1303606

#TimeUsernameProblemLanguageResultExecution timeMemory
1303606activedeltorreRobots (IOI13_robots)C++20
14 / 100
1262 ms12652 KiB
#include "robots.h"
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
struct ura
{
    int timp,tip;
};
vector<ura>event;
vector<int>ram;
int solve(int mij)
{
    priority_queue<int>pq;
    for(int i=0;i<event.size();i++)
    {
        auto curr=event[i];
        if(curr.tip==-1)
        {
            int cnt=mij;
            while(pq.size() && cnt>=1)
            {
                pq.pop();
                cnt--;
            }
        }
        else
        {
            pq.push(curr.tip);
        }
    }
    for(int i=ram.size()-1;i>=0;i--)
    {
        int cnt=mij;
        while(pq.size() && cnt>=1 && pq.top()<ram[i])
        {
            pq.pop();
            cnt--;
        }
    }
    if(pq.size()==0)
    {
        return 1;
    }
    while(pq.size())
    {
        pq.pop();
    }
    return 0;
}
bool cmp(ura a,ura b)
{
    if(a.timp==b.timp)
    {
        return a.tip>b.tip;
    }
    return a.timp<b.timp;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    int st=1,dr=1000000;
    for(int i=0;i<T;i++)
    {
        S[i]++;
        W[i]++;
        event.push_back({S[i],W[i]});
    }
    for(int i=0;i<B;i++)
    {
        event.push_back({Y[i],-1});
    }
    for(int i=0;i<A;i++)
    {
        ram.push_back(X[i]);
    }
    sort(ram.begin(),ram.end());
    sort(event.begin(),event.end(),cmp);
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(solve(mij)==1)
        {
            dr=mij-1;
        }
        else
        {
            st=mij+1;
        }
    }
    if(dr+1>=1000000)
    {
        dr=-2;
    }
    return dr+1;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...