Submission #388332

#	Time	Username	Problem	Language	Result	Execution time	Memory
388332		ivan24	Robots (IOI13_robots)	C++14	76 / 100	728 ms	18524 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
#define F first
#define S second
typedef vector<ii> vii;
typedef vector<vii> vvii;

class Solver{
private:
    ll a,b,t;
    vi x,y,w,s;
    vii szwt;
    bool works (ll mins){
        //cout << mins << endl;
        if (mins*(a+b) < t) return 0;
        vi xcur, ycur;
        for (ll i = a-1; i >= 0; i--){
            for (ll j = 0; mins > j; j++){
                xcur.push_back(x[i]);
                if (xcur.size() == t) break;
            }
            if (xcur.size() == t) break;
        }
        for (ll i = b-1; i >= 0; i--){
            for (ll j = 0; mins > j; j++){
                ycur.push_back(y[i]);
                if (ycur.size() == t) break;
            }
            if (ycur.size() == t) break;
        }
        reverse(xcur.begin(),xcur.end());
        reverse(ycur.begin(),ycur.end());
        /*
        for (auto i: xcur) cout << i << ' ';
        cout << endl;
        for (auto i: ycur) cout << i << ' ';
        cout << endl;
        */

        ll ptr = 0;
        priority_queue<ll> pq;
        for (ll i = 0; xcur.size() > i; i++){
            while (t > ptr && xcur[i] > szwt[ptr].F){
                pq.push(szwt[ptr].S);
                ptr++;
            }
            if (!pq.empty()){
                //cout << xcur[i] << ": " << pq.top() << endl;
                pq.pop();
            }
        }
        while (t > ptr){
            pq.push(szwt[ptr].S);
            ptr++;
        }
        for (ll i = ycur.size()-1; i >= 0; i--){
            if (pq.empty()) break;
            if (ycur[i] > pq.top()){ pq.pop(); }
        }

        return pq.empty();
    }
public:
    Solver(ll _a, ll _b, ll _t, ll _x[], ll _y[], ll _w[], ll _s[]): a(_a), b(_b), t(_t){
        x.resize(a); y.resize(b);
        w.resize(t); s.resize(t);
        szwt.resize(t);
        for (ll i = 0; a > i ;i++) x[i] = _x[i];
        for (ll i = 0; b > i ;i++) y[i] = _y[i];
        for (ll i = 0; t > i; i++){
            w[i] = _w[i];
            s[i] = _s[i];
            szwt[i] = ii(w[i], s[i]);
        }

    }
    ll solve(){
        sort(x.begin(),x.end());
        sort(y.begin(),y.end());
        sort(szwt.begin(),szwt.end());

        for (auto i: szwt){
            ll maxX = 0;
            if (a > 0) maxX = x[a-1];
            ll maxY = 0;
            if (b > 0) maxY = y[b-1];
            if (i.F >= maxX && i.S >= maxY) return -1;
        }

        ll lo = 1, hi = t, md = (1+t)/2;
        while (hi >= lo){
            md = (lo+hi)/2;
            if (lo == hi) break;
            ll res = works(md);
            //cout << "md: " << md << " res: " << res << endl;
            if (res){
                hi = md;
            }else{
                lo = md+1;
            }
        }
        return md;
    }
};
int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]) {
    Solver mySolver(a,b,t,x,y,w,s);
    return mySolver.solve();
}

Compilation message (stderr)

robots.cpp: In member function 'bool Solver::works(ll)':
robots.cpp:25:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   25 |                 if (xcur.size() == t) break;
      |                     ~~~~~~~~~~~~^~~~
robots.cpp:27:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   27 |             if (xcur.size() == t) break;
      |                 ~~~~~~~~~~~~^~~~
robots.cpp:32:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   32 |                 if (ycur.size() == t) break;
      |                     ~~~~~~~~~~~~^~~~
robots.cpp:34:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   34 |             if (ycur.size() == t) break;
      |                 ~~~~~~~~~~~~^~~~
robots.cpp:47:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   47 |         for (ll i = 0; xcur.size() > i; i++){
      |                        ~~~~~~~~~~~~^~~

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