Submission #897942

#	Time	Username	Problem	Language	Result	Execution time	Memory
897942		Sir_Ahmed_Imran	Robots (IOI13_robots)	C++17	90 / 100	3079 ms	31412 KiB

robots

                              ///~~~LOTA~~~///
#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long 
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
bool check(int t,vector<pii>& v,multiset<int>& a,multiset<int>& b,int d){
    map<int,int> A,B;
    for(auto& i:a)
        A[i]+=d;
    for(auto& i:b)
        B[i]+=d;
    int u[t];
    for(int i=0;i<t;i++)
        u[i]=0;
    for(int i=t-1;i>=0;i--){
        int x=(*A.upper_bound(v[i].ff)).ff;
        if(x!=INT_MAX){
            A[x]--;
            if(A[x]==0)
                A.erase(A.upper_bound(v[i].ff));
            u[i]=1;
        }
    }
    int z=0;
    for(int i=t-1;i>=0;i--){
        int x=(*B.upper_bound(v[i].ss)).ff;
        if(x!=INT_MAX){
            B[x]--;
            if(B[x]==0)
                B.erase(B.upper_bound(v[i].ss));
            z+=u[i];
        }
        else if(u[i]==0){
            if(z>0) z--;
            else return 0;
        }
    }
    return 1;
}
int putaway(int n,int m,int t,int x[],int y[],int w[],int s[]){
    vector<pii> v;
    for(int i=0;i<t;i++)
        v.append({w[i],s[i]});
    sort(all(v));
    multiset<int> a,b;
    for(int i=0;i<n;i++)
        a.insert(x[i]);
    for(int i=0;i<m;i++)
        b.insert(y[i]);
    a.insert(INT_MAX);
    b.insert(INT_MAX);
    int o=0,r=0;
    for(int i=524288;i>0;i/=2){
        if(check(t,v,a,b,o+i)) r=1;
        else o+=i; 
    }
    if(r==0) return -1;
    return o+1;
}

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