Submission #262872

#	Time	Username	Problem	Language	Result	Execution time	Memory
262872		uacoder123	Robots (IOI13_robots)	C++14	100 / 100	2227 ms	34600 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!=pj+1)
                    {
                      s.insert(v4.begin()+pj+1,v4.begin()+j);
                      pj=j-1;
                    }
                    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(v1[i],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 l=(t)/(a+b),r=t,ans=t+1;
                  while(l<=r)
                  {
                    int m=(l+r)/2;
                    s.clear();
                    if(check(m))
                    {
                      r=m-1;
                      ans=m;
                    }
                    else
                      l=m+1;
                  }
                  return (ans<=t)?ans:-1;
                }

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