Submission #962650

#	Time	Username	Problem	Language	Result	Execution time	Memory
962650		Ice_man	Robots (IOI13_robots)	C++14	100 / 100	1802 ms	35236 KiB

robots

/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include"robots.h"
#include <map>
#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <cstdio>

#define maxn 2000005
#define maxn2 205
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cerr<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")

using namespace std;

/**std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}*/

typedef pair <int, int> pii;

int a , b , t;
int w[maxn] , s[maxn];

int x[maxn] , y[maxn];
pii pom[maxn];


bool check(int time)
{
    int pomm = 1 , idx = a - 1;
    map <int , int> m;

    for(int i = 0; i < b; i++)
        m[i] = time;
    long long tt = 0;

    for(int i = t - 1; i > -1; i--)
    {
        while(idx > -1 && idx >= pom[i].X)
        {
            idx--;
            tt += time;
        }

        auto it = m.lower_bound(pom[i].Y);
        if(it == m.end())
            tt--;
        else
        {
            --((*it).Y);
            if((*it).Y == 0)
                m.erase(it);
        }

        if(tt < 0)
        {
            pomm = 0;
            break;
        }
    }

    return pomm;
}






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 < t; i++)
    {
        w[i] = W[i];
        s[i] = S[i];
    }

    for(int i = 0; i < a; i++)
        x[i] = X[i];
    for(int i = 0; i < b; i++)
        y[i] = Y[i];

    sort(x , x + a);
    sort(y , y + b);

    for(int i = 0; i < t; i++)
        pom[i] = {upper_bound(x , x + a , w[i]) - x , upper_bound(y , y + b , s[i]) - y};
    sort(pom , pom + t);


    int l = 1;
    int r = t + 1;
    int mid;
    while(l < r)
    {
        mid = (l + r) / 2;

        if(check(mid) == true)
            r = mid;
        else
            l = mid + 1;
    }


    if(l == t + 1)
        return -1;
    return l;

}



/**int main()
{

    #ifdef ONLINE_JUDGE /// promeni
        freopen("input.in", "r", stdin);
        freopen("taxi.out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    //startT = std::chrono::high_resolution_clock::now();





    return 0;
}*/

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