Submission #205985

#	Time	Username	Problem	Language	Result	Execution time	Memory
205985		gratus907	Robots (IOI13_robots)	C++17	100 / 100	2605 ms	47652 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ll long long
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using pii = pair<int, int>;

struct toy
{
    int w, s, ind;
    void print()
    {
        printf("Toy %d : Weight %d, Size %d\n",ind,w,s);
    }
};
bool by_weight(toy &a, toy &b)
{
    return a.w < b.w;
}
bool by_size(toy &a, toy &b)
{
    return a.s < b.s;
}
vector <toy> toy_w, toy_s;
vector <int> weak;
vector <int> small;
toy all_toy[1010101];
bool took[1010101];
int a, b, t;
const bool debug = false;
priority_queue<pii> pq;
bool check(int x)
{
    memset(took, 0, sizeof(took));
    int pt = 0;
    for (int i = 0; i<a; i++)
    {
        while(pt<t && toy_w[pt].w < weak[i])
        {
            pq.push({toy_w[pt].s, toy_w[pt].ind});
            pt++;
        }
        int gt = 0;
        while(gt<x && !pq.empty())
        {
            took[pq.top().second] = true;
            pq.pop();
            gt++;
        }
    }
    while(pt<t)
    {
        pq.push({toy_w[pt].s, toy_w[pt].ind});
        pt++;
    }
    vector <pii> temp;
    while(!pq.empty())
    {
        temp.push_back(pq.top());
        pq.pop();
    }
    for (int i = 0; i<b; i++)
    {
        int gt = 0;
        while(gt<x && !temp.empty() && temp.back().first < small[i])
        {
            took[temp.back().second] = true;
            temp.pop_back();
            gt++;
        }
    }
    for (int i = 0; i<t; i++)
    {
        if (took[i]==0) 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++)
    {
        int x; x = X[i];
        weak.push_back(x);
    }
    for (int i = 0; i<b; i++)
    {
        int x; x = Y[i];
        small.push_back(x);
    }
    sort(all(weak));
    sort(all(small));
    for (int i = 0; i<t; i++)
    {
        int ww, ss;
        ww = W[i], ss = S[i];
        toy_w.push_back({ww, ss, i});
        toy_s.push_back({ww, ss, i});
        all_toy[i] = {ww, ss, i};
    }
    sort(all(toy_w),by_weight);
    sort(all(toy_s),by_size);
    int lo = 1, hi = 1e6+1;
    if (!check(1e6+1))
    {
        return -1;
    }
    while(lo + 1 < hi)
    {
        int mid = (lo + hi)/2;
        if (check(mid))
            hi = mid;
        else lo = mid;
    }
    return (check(lo)?lo:hi);
}

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