Submission #70748

#	Time	Username	Problem	Language	Result	Execution time	Memory
70748		MANcity	Robots (IOI13_robots)	C++14	100 / 100	2516 ms	13504 KiB

robots

#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
#include "robots.h"
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
int T;
int A;
int B;
pair<int,int> Sx[2000002];
int X[2000002];
int Y[2000002];
int check(int CH_time)
{
    priority_queue<int> myq;
    int mypos=0;
    for0(i,A-1)
    {
        fo(j,mypos,T-1)
        {
            if(X[i]>Sx[j].first)
            {
                myq.push(Sx[j].second);
                if(j==(T-1))
                    mypos=T;
            }
            else
            {
                mypos=j;
                break;
            }
        }
        int han_qan=0;
        while(!myq.empty())
        {
            han_qan++;
            myq.pop();
            if(han_qan>=CH_time)
                break;
        }
    }
    fo(j,mypos,T-1)
        myq.push(Sx[j].second);
    if(myq.empty())
        return 1;
    fr(i,B-1,0)
    {
        int han_qan=0;
        while(!myq.empty())
        {
            int TOP=myq.top();
            if(Y[i]>TOP)
            {
                han_qan++;
                myq.pop();
            }
            else
                return 0;
            if(han_qan>=CH_time)
                break;
        }
    }
    if(myq.empty())
        return 1;
    return 0;
}
int putaway(int A_0, int B_0, int T_0, int X_0[], int Y_0[], int W[], int S[]) {
    A=A_0;
    B=B_0;
    T=T_0;
    for0(i,A-1)
        X[i]=X_0[i];
    for0(i,B-1)
        Y[i]=Y_0[i];
    for0(i,T-1)
        Sx[i]=mp(W[i],S[i]);
    sort(Sx,Sx+T);
    sort(X,X+A);
    sort(Y,Y+B);
    if(check(T)==0)
        return -1;
    int l=1;
    int r=(T);
    while(1)
    {
        if(l==r)
            return l;
        int m=(l+r)/2;
        if(check(m)==1)
            r=m;
        else
            l=(m+1);
    }
}
/*
3 2 10
6 2 9
4 7
4 6
8 5
2 3
7 9
1 8
5 1
3 3
8 7
7 6
10 5
*/
/*
2 1 3
2 5
2
3 1
5 3
2 2
*/

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