제출 #1162051

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162051		AlgorithmWarrior	로봇 (IOI13_robots)	C++20	76 / 100	3095 ms	32304 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"

using namespace std;

int const MAX=1e6+5;

struct w_s{
    int w,s;
    bool operator<(w_s ot){
        return s>ot.s;
    }
}toy[MAX];

bool cmp(int a,int b){
    return a>b;
}

bool check(int days,int X[],int Y[],int A,int B,int T){
    multiset<int>ms;
    int i,j;
    for(i=0;i<A;++i)
        if(1LL*i*days<T){
            for(j=0;j<days;++j)
                ms.insert(X[i]);
        }
    vector<int>v;
    for(i=0;i<T;++i)
        if(ms.upper_bound(toy[i].w)==ms.end())
            v.push_back(toy[i].s);
        else{
            int nr=*ms.upper_bound(toy[i].w);
            ms.erase(ms.find(nr));
        }
    if(1LL*B*days<(int)v.size())
        return 0;
    for(i=0;i*days<(int)v.size();++i)
        if(v[i*days]>=Y[i])
            return 0;
    return 1;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    sort(X,X+A,cmp);
    sort(Y,Y+B,cmp);
    int i;
    for(i=0;i<T;++i)
        toy[i]={W[i],S[i]};
    sort(toy,toy+T);
    for(i=0;i<T;++i)
        if(toy[i].w>=X[0] && toy[i].s>=Y[0])
            return -1;
    /// (]
    int st=0,dr=T;
    while(dr-st>1){
        int mij=(st+dr)/2;
        if(check(mij,X,Y,A,B,T))
            dr=mij;
        else
            st=mij;
    }
    return dr;
}

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