제출 #419302

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
419302		TLP39	로봇 (IOI13_robots)	C++14	100 / 100	814 ms	22300 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long int ll;
int a,b,t;
int x[50010],y[50010];
pii ty[1000010];


int bs_x(int val)
{
    if(x[a]<=val) return a+1;
    int hi=a,low=1,av;
    while(hi>low)
    {
        av=(hi+low)>>1;
        if(x[av]>val) hi=av;
        else low=av+1;
    }
    return hi;
}

int bs_y(int val)
{
    if(y[b]<=val) return b+1;
    int hi=b,low=1,av;
    while(hi>low)
    {
        av=(hi+low)>>1;
        if(y[av]>val) hi=av;
        else low=av+1;
    }
    return hi;
}
priority_queue<int> pq;
bool test_min(int k)
{
    while(!pq.empty()) pq.pop();
    int id=1,cou,to;
    for(int i=1;i<=a;i++)
    {
        while(id<=t && ty[id].first==i)
        {
            pq.push(ty[id].second);
            id++;
        }
        cou=k;
        while(cou && !pq.empty())
        {
            pq.pop();
            cou--;
        }
    }
    while(id<=t)
    {
        pq.push(ty[id].second);
        id++;
    }
    int co=0;
    while(!pq.empty())
    {
        to=pq.top();
        pq.pop();
        co++;
        if((ll)co>(ll)k*(ll)(b+1-to)) return false;
    }
    return true;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    a=A;
    b=B;
    t=T;
    for(int i=0;i<a;i++) x[i+1]=X[i];
    for(int i=0;i<b;i++) y[i+1]=Y[i];
    sort(x+1,x+a+1);
    sort(y+1,y+b+1);
    for(int i=0;i<t;i++)
    {
        ty[i+1]={bs_x(W[i]),bs_y(S[i])};
        if(ty[i+1].first==a+1 && ty[i+1].second==b+1) return -1;
    }
    sort(ty+1,ty+t+1);
    int hi=t,low=1,av;
    while(hi>low)
    {
        av=(hi+low)>>1;
        if(test_min(av)) hi=av;
        else low=av+1;
    }
    return hi;
}

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