Submission #574111

#	Time	Username	Problem	Language	Result	Execution time	Memory
574111		MohamedAliSaidane	Robots (IOI13_robots)	C++14	100 / 100	1432 ms	24748 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> ti;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ld,ld> pld;
#define pb push_back
#define popb pop_back()
#define pf push_front
#define popf pop_front
#define ff first
#define ss second
#define MOD (ll)(1000000007)
#define INF (ll) (1e18)
#define all(v) (v).begin(),(v).end()
const int nx[8] = {0, 0, 1, -1,1,1,-1,-1}, ny[8] = {1, -1, 0, 0,1,-1,1,-1}; //East, West, South, North+
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
ll lcm(ll a, ll b){return (a / gcd(a, b)) * b;}
////////////******SOLUTION******\\\\\\\\\\\
 
//const int MAX_T = 1e6 + 4;
//const int MAX_N = 5e4 + 4;
 
int A, B, T;
vi X,Y;
vector<pii> byW;
bool comp(pii a, pii b)
{
    if(a.ff == b.ff)
        return a.ss > b.ss;
    else
        return a.ff < b.ff;
}
 
bool test(int x)
{
    priority_queue<int> pq;
    int time = 0;
    int j = 0;
    for(int i = 0; i< A; i ++)
    {
        int time = 0;
        for(;j <T &&  byW[j].ff < X[i]; j ++)
            pq.push(byW[j].ss);
        while(time < x && !pq.empty())
        {
            pq.pop();
            time ++;
        }
    }
    for(;j<T;j++)
        pq.push(byW[j].ss);
    if(pq.size() > B * x)
        return 0;
    for(int i = B-1; i >= 0 && !pq.empty();i--)
    {
        if(Y[i] <= pq.top())
            return 0;
        for(int t = 0; t < x && !pq.empty();t++)
            pq.pop();
    }
    return pq.empty();
}
 
int putaway(int a, int b, int t, int x[], int y[], int w[], int s[])
{
    A = a, B = b, T = t;
    for(int i = 0; i < A; i ++)
        X.pb(x[i]);
    for(int i = 0; i < B; i ++)
        Y.pb(y[i]);
    for(int i = 0; i < T; i ++)
        byW.pb({w[i],s[i]});
    sort(all(X));
    sort(all(Y));
    sort(byW.begin(),byW.end(),comp);
    int wmax = 0;
    int smax = 0;
    wmax = A == 0? 0:X[A-1];
    smax = B == 0? 0:Y[B-1];
    for(int i = 0; i < T; i ++)
        if(byW[i].ff >= wmax && byW[i].ss >= smax)
            return -1;
    if(B == 0)
    {
        int debut = 1;
        int fin = T;
        int ans = T;
        sort(w,w+T);
        while(debut <= fin)
        {
            int mid = (debut+fin)/2;
            bool flag= true;
            int i = A-1;
            int j = T -1;
            while(j >= 0)
            {
                if(i < 0 || w[j] >= X[i])
                {
                    flag=false;
                    break;
                }
                j -= mid;
                i--;
            }
            if(flag)
            {
                ans = mid;
                fin = mid -1;
            }
            else
                debut = mid + 1;
        }
        return ans;
    }
    //for(int i = 0; i < T; i ++)
        //cout << byW[i].ff << ' ' << byW[i].ss << '\n';
    //cout << '\n';
    //sort(byS,byS+T,how);
    int debut = 1;
    int fin = T;
    int ans = T;
    while(debut <= fin)
    {
        int mid = (debut+fin)/2;
        if(test(mid))
        {
            ans = mid;
            fin = mid - 1;
        }
        else
            debut = mid + 1;
    }
    return ans;
 
}
/*
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int A, B, T;
    cin >> A >> B >> T;
    int X[A], Y[B], W[T], S[T];
    for(int i = 0; i < A; i ++)
    {
        int x; cin >> x;
        X[i]=x;
    }
    for(int i = 0; i< B; i ++)
    {
        int y; cin >> y;
        Y[i]=y;
    }
    for(int i = 0;  i < T; i ++)
    {
        int w, s;
        cin >> w >> s;
        W[i] = w;
        S[i] = s;
    }
    cout << putaway(A,B,T,X,Y,W,S) << '\n';
}
/*
5 0 6
2 3 4 5 6
1 80
2 80
3 80
4 80
1 80
5 80
*/
/*
3 2 10
6 2 9
4 7
4 6
8 5
2 3
7 9
1 8
5 1
3 3
8 7
7 6
10 5
*/

Compilation message (stderr)

robots.cpp:25:1: warning: multi-line comment [-Wcomment]
   25 | ////////////******SOLUTION******\\\\\\\\\\\
      | ^
robots.cpp:170:1: warning: "/*" within comment [-Wcomment]
  170 | /*
      |  
robots.cpp: In function 'bool test(int)':
robots.cpp:59:18: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |     if(pq.size() > B * x)
      |        ~~~~~~~~~~^~~~~~~
robots.cpp:44:9: warning: unused variable 'time' [-Wunused-variable]
   44 |     int time = 0;
      |         ^~~~

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