Submission #262851

#	Time	Username	Problem	Language	Result	Execution time	Memory
262851		uacoder123	Robots (IOI13_robots)	C++14	0 / 100	330 ms	65540 KiB

robots

            #include <bits/stdc++.h>
#include "robots.h"

            using namespace std;
            #define F first
            #define S second
            #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
            #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
            #define all(x) (x).begin(), (x).end()
            #define sz(x) int(x.size())
            #define mp(i,a) make_pair(i,a)
            #define pb(a) push_back(a)
            #define bit(x,b) (x&(1LL<<b))
             
            typedef pair <int,int> ii;
            typedef pair <int,ii> iii;
            typedef vector <int> vi;
            int t,a,b;
            vector<ii> v;
            vi v1,v2,v4;
            multiset<int> s;
            bool cmp(ii a,ii b)
            {
              return a.S<b.S;
            }
            int check(int m)
            {
              int j=0,pj=-1;
              for(int i=0;i<a;++i)
              {
                while(j!=t&&v[j].F<v1[i])
                  j++;
                if(j!=0)
                {
                  s.insert(v4.begin()+pj+1,v4.begin()+j);
                  pj=j;
                }
                int co=0;
                while(co!=m&&s.size())
                {
                  s.erase(((--s.end())));
                  co++;
                }
              }
              if(pj<t-1)
              {
                s.insert(v4.begin()+pj+1,v4.end());
              }
              for(int i=0;i<b;++i)
              {
                int co=0;
                if(!s.size())
                  return 1;
                while(co!=m&&s.size()&&(*s.begin())<v2[i])
                {
                  s.erase((s.begin()));
                  co++;
                }
              }
              if(s.size())
                return 0;
              return 1;
            }
            int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
            {
              t=T;
              a=A;
              b=B;
              for(int i=0;i<a;++i)
                v1.pb(X[i]);
              for(int i=0;i<b;++i)
                v2.pb(Y[i]);
              for(int i=0;i<t;++i)
                v.pb(mp(W[i],S[i]));
              sort(all(v));
              sort(all(v1));
              sort(all(v2));
              int la=-1;
              for(int i=0;i<a;++i)
              {
                auto it=lower_bound(all(v),mp(v[i].F,0))-v.begin();
                it--;
                if(it!=la)
                {
                  sort(v.begin()+la+1,v.begin()+it+1,cmp);
                  la=it;
                }
              }
              if(la!=t-1)
                sort(v.begin()+la+1,v.end(),cmp);
              for(int i=0;i<t;++i)
                v4.pb(v[i].S);
              int ma=0;
              for(int i=t-1;i>=0;--i)
              {
                if(v1.size()&&(v[i].F<v1.back()))
                  break;
                else
                  ma=max(v[i].S,ma);
              }
              if(v2.size()&&ma>=v2.back())
                return -1;
              int l=(t)/(a+b),r=t,ans=t;
              while(l<=r)
              {
                int m=(l+r)/2;
                s.clear();
                if(check(m))
                {
                  r=m-1;
                  ans=m;
                }
                else
                  l=m+1;
              }
              return ans;
            }

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