Submission #242511

#	Time	Username	Problem	Language	Result	Execution time	Memory
242511		Dremix10	Robots (IOI13_robots)	C++17	100 / 100	2424 ms	36876 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define F first
#define S second
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define maxp 22
#define EPS (ld)(1e-18)
#define mod (int)(1e9+7)
#define N (int)(1e6+1)

struct ano{

int w;
int s;
int id;

};

bool cmpW(ano a, ano b){
    if(a.w==b.w)
        return a.s>b.s;
    return a.w<b.w;
}

bool cmpS(ano a, ano b){
    if(a.s==b.s)
        return a.w>b.w;
    return a.s<b.s;
}

ano sortw[N];
ano sorts[N];

bool chk(ll x, int w[],int s[], int n, int weak, int small){
    int i;
    bool v[n];
    memset(v,0,sizeof v);

    int cnt=0;

    priority_queue<pair<int,int> > q;
    int pos=0;

    for(i=0;i<weak;i++){

        while(pos<n && sortw[pos].w<w[i]){
            q.push({sortw[pos].s,sortw[pos].id});
            pos++;
        }
        int temp=x;
        while(q.size() && temp--){
            v[q.top().S]=1;
            cnt++;
            q.pop();
        }

    }
    while(q.size())
        q.pop();
    //q.clear();
    pos=0;

    for(i=0;i<small;i++){

        while(pos<n && sorts[pos].s<s[i]){
            if(!v[sorts[pos].id])
                q.push({sorts[pos].w,sorts[pos].id});
            pos++;
        }
        int temp=x;
        while(q.size() && temp--){
            v[q.top().S]=1;
            cnt++;
            q.pop();
        }

    }
    if(cnt==n)
        return true;
    return false;

}



int putaway(int weak, int small, int n, int w[], int s[], int arrW[], int arrS[]) {
    int i;
    sort(w,w+weak);
    sort(s,s+small);

    for(i=0;i<n;i++){
        ano temp={arrW[i],arrS[i],i};
        sortw[i]=temp;
        sorts[i]=temp;
    }
    sort(sortw,sortw+n,cmpW);
    sort(sorts,sorts+n,cmpS);

    int bigw=-1;
    if(weak)
        bigw=w[weak-1];

    int bigs=-1;
    if(small)
        bigs=s[small-1];

    bool ok=0;

    if(bigw<=sortw[n-1].w && bigs<=sortw[n-1].s)
        ok=1;
    if(bigw<=sorts[n-1].w && bigs<=sorts[n-1].s)
        ok=1;

    if(ok)
        return -1;

    ll l=1,r=n;
    int ans=n;

    while(l<=r){
        ll mid=(l+r)/2;
        bool ok=chk(mid,w,s,n,weak,small);
        if(ok){
            ans=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    return ans;
}

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