제출 #587216

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587216		FatihSolak	로봇 (IOI13_robots)	C++17	100 / 100	1836 ms	65536 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
vector<int> x,y;
vector<pair<int,int>> toys;
int a,b,t;
int cnt[N];
int deltime[N];
vector<int> v[N];
bool ck(int x){
    if(b == 1){
        int tot = 0;
        for(int i = 0;i<t;i++){
            tot++;
            long long val = (long long)cnt[i] * x;
            while(val && tot){
                val--;
                tot--;
            }
        }
        return tot == 0;
    }
    priority_queue<int> rem;
    for(int i = 0;i<t;i++){
        rem.push(toys[i].second);
        long long val = (long long)cnt[i] * x;
        while(val && rem.size()){
            val--;
            rem.pop();
        }
    }
    for(int i = b-1;i>=0;i--){
        int val = x;
        while(val && rem.size() && rem.top() < y[i]){
            val--;
            rem.pop();
        }
    }
    return rem.empty();
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
    x.push_back(1);
    y.push_back(1);
    for(int i = 0;i<A;i++){
        x.push_back(X[i]);
    }
    for(int i = 0;i<B;i++){
        y.push_back(Y[i]);
    }
    vector<int> compressx = x,compressy = y;
    for(int i = 0;i<T;i++){
        toys.push_back({W[i],S[i]});
        compressx.push_back(W[i]);
        compressy.push_back(S[i]);
    }
    sort(compressx.begin(),compressx.end());
    sort(compressy.begin(),compressy.end());
    compressx.resize(unique(compressx.begin(),compressx.end())-compressx.begin());
    compressy.resize(unique(compressy.begin(),compressy.end())-compressy.begin());
    for(auto &u:x){
        u = lower_bound(compressx.begin(),compressx.end(),u) - compressx.begin();
    }
    for(auto &u:y){
        u = lower_bound(compressy.begin(),compressy.end(),u) - compressy.begin();
    }
    for(auto &u:toys){
        u.first = lower_bound(compressx.begin(),compressx.end(),u.first) - compressx.begin();
        u.second = lower_bound(compressy.begin(),compressy.end(),u.second) - compressy.begin();
    }
    a = A+1;
    b = B+1;
    t = T;
    sort(x.begin(),x.end());
    sort(y.begin(),y.end());
    sort(toys.begin(),toys.end());
    for(auto u:toys){
        if(u.first >= x.back() && u.second >= y.back()){
            return -1;
        }
    }
    for(int i = 0;i<t;i++){
        v[toys[i].second].push_back(i);
    }

     
    int pt = 0;
    for(auto u:x){
        while(pt < t && toys[pt].first < u){
            pt++;
        }
        if(pt)
            cnt[pt-1]++;
    }
    int l = 1,r = t;
    while(l < r){
        int m = (l+r)/2;
        if(ck(m)){
            r = m;
        }
        else l = m+1;
    }
    return l;
}

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