Submission #70667

#	Time	Username	Problem	Language	Result	Execution time	Memory
70667		MANcity	Robots (IOI13_robots)	C++14	14 / 100	1615 ms	66560 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;
    pair<LL,pair<LL,int> > Sx[1000010];
    pair<LL,pair<LL,int> > Sy[1000010];
    int posx[1000010];
    int posy[1000010];
    pair<LL,int> tx[5*1000002];
    pair<LL,int> ty[5*1000002];
    void update_x(int left,int right,int pos,int v,LL val)
    {
        if(left==right)
            tx[v]=mp(val,left);
        else
        {
            int m=(left+right)/2;
            if(pos<=m)
                update_x(left,m,pos,2*v,val);
            else
                update_x(m+1,right,pos,2*v+1,val);
            tx[v]=max(tx[2*v],tx[2*v+1]);
        }
    }
    pair<LL,int> getmax_x(int left,int right,int l,int r,int v)
    {
        if(l>r)
            return {-1,-1};
        if(left==l && right==r)
            return tx[v];
        int m=(left+right)/2;
        pair<LL,int> A=getmax_x(left,m,l,min(r,m),2*v);
        pair<LL,int> B=getmax_x(m+1,right,max(l,m+1),r,2*v+1);
        return max(A,B);
    }
    void update_y(int left,int right,int pos,int v,LL val)
    {
        if(left==right)
            ty[v]=mp(val,left);
        else
        {
            int m=(left+right)/2;
            if(pos<=m)
                update_y(left,m,pos,2*v,val);
            else
                update_y(m+1,right,pos,2*v+1,val);
            ty[v]=max(ty[2*v],ty[2*v+1]);
        }
    }
    pair<LL,int> getmax_y(int left,int right,int l,int r,int v)
    {
        if(l>r)
            return {-1,-1};
        if(left==l && right==r)
            return ty[v];
        int m=(left+right)/2;
        pair<LL,int> A=getmax_y(left,m,l,min(r,m),2*v);
        pair<LL,int> B=getmax_y(m+1,right,max(l,m+1),r,2*v+1);
        return max(A,B);
    }
    int bin_x(LL VAL)
    {
        int l=0;
        int r=T-1;
        while(1)
        {
            if(l==r)
                return l;
            int m=(l+r+1)/2;
            if(Sx[m].first<VAL)
                l=m;
            else
                r=(m-1);
        }
    }
    int bin_y(LL VAL)
    {
        int l=0;
        int r=T-1;
        while(1)
        {
            if(l==r)
                return l;
            int m=(l+r+1)/2;
            if(Sy[m].first<VAL)
                l=m;
            else
                r=(m-1);
        }
    }
    int putaway(int A, int B, int T_0, int X[], int Y[], int W[], int S[]) {
        T=T_0;
        for0(i,T-1)
            Sx[i]={W[i],{i+1,i}};
        for0(i,T-1)
            Sy[i]={S[i],{W[i],i}};
        sort(Sx,Sx+T);
        sort(Sy,Sy+T);
        for0(i,T-1)
            update_x(0,T-1,i,1,Sx[i].second.first);
        for0(i,T-1)
        {
            update_y(0,T-1,i,1,Sy[i].second.first);
        }
        for0(i,T-1)
        {
            posx[Sx[i].second.second]=i;
            posy[Sy[i].second.second]=i;
        }
        sort(X,X+A);
        sort(Y,Y+B);
        LL Time=0;
        int qan=0;
        /*for0(i,T-1)
            cout<<Sx[i].first<<" ";
        cout<<endl;
        for0(i,T-1)
            cout<<Sx[i].second.first<<" ";
        cout<<endl;
        cout<<endl;
        for0(i,T-1)
            cout<<Sy[i].first<<" ";
        cout<<endl;
        for0(i,T-1)
            cout<<Sy[i].second.first<<" ";
        cout<<endl;
        cout<<endl;*/
        int f=0;
        while(1)
        {
            int u=0;
            for0(i,A-1)
            {
                if(Sx[0].first<X[i])
                {
                    int myx=bin_x(X[i]);
                    pair<LL,int> max_bef=getmax_x(0,T-1,0,myx,1);
                    if(max_bef.first>0)
                    {
                        u=1;
                        qan++;
                        int pos_bef=max_bef.second;
                        update_x(0,T-1,pos_bef,1,-1);
                        int pos_y=Sx[pos_bef].second.second;
                        update_y(0,T-1,posy[pos_y],1,-1);
                    }
                }
            }
            for0(i,B-1)
            {
                if(Sy[0].first<Y[i])
                {
                    int myy=bin_y(Y[i]);
                    pair<LL,int> max_bef=getmax_y(0,T-1,0,myy,1);
                    if(max_bef.first>0)
                    {
                        u=1;
                        qan++;
                        int pos_bef=max_bef.second;
                        update_y(0,T-1,pos_bef,1,-1);
                        int pos_x=Sy[pos_bef].second.second;
                        update_x(0,T-1,posx[pos_x],1,-1);
                    }
                }
            }
            /*cout<<endl;
            cout<<endl;
            int r;
            cin>>r;*/
     
            if(u==0)
                f++;
            if(f>=30)
                return (-1);
            Time++;
            if(qan==T)
                return Time;
        }
    }

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