Submission #897946

#	Time	Username	Problem	Language	Result	Execution time	Memory
897946		Sir_Ahmed_Imran	Robots (IOI13_robots)	C++17	90 / 100	3050 ms	19900 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()
int u[1000000];
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;
    for(int i=t-1;i>=0;i--){
        u[i]=0;
        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[]){
    int mx,my;
    vector<pii> v;
    multiset<int> a,b;
    a.insert(INT_MAX);
    b.insert(INT_MAX);
    for(int i=mx=0;i<n;i++){
        a.insert(x[i]);
        mx=max(mx,x[i]);
    }
    for(int i=my=0;i<m;i++){
        b.insert(y[i]);
        my=max(my,y[i]);
    }
    for(int i=0;i<t;i++){
        v.append({w[i],s[i]});
        if(w[i]>=mx && s[i]>=my)
            return -1;
    }
    sort(all(v));
    int o=0;
    for(int i=524288;i>0;i/=2)
        if(!check(t,v,a,b,o+i))
            o+=i; 
    return o+1;
}

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