제출 #262869

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
262869		uacoder123	Robots (IOI13_robots)	C++14	100 / 100	2542 ms	46236 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=1,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