Submission #242255

#	Time	Username	Problem	Language	Result	Execution time	Memory
242255		Dremix10	Robots (IOI13_robots)	C++17	90 / 100	533 ms	17016 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;

    int pos=0;
    int curr=0;
    for(i=0;i<n;i++){
        if(pos>=weak)
            break;

        if(w[pos]>sortw[i].w){
            curr++;
            v[sortw[i].id]=true;
            cnt++;
            if(curr==x){
                curr=0;
                pos++;
            }
        }
    }

    pos=0;
    curr=0;
    for(i=0;i<n;i++){
        if(pos>=small)
            break;

        if(!v[sorts[i].id] && s[pos]>sorts[i].s){
            curr++;
            v[sorts[i].id]=true;
            cnt++;
            if(curr==x){
                curr=0;
                pos++;
            }
        }
    }
    if(cnt==n)
        return true;

    memset(v,0,sizeof v);
    cnt=0;


    pos=0;
    curr=0;
    for(i=0;i<n;i++){
        if(pos>=small)
            break;

        if(!v[sorts[i].id] && s[pos]>sorts[i].s){
            curr++;
            v[sorts[i].id]=true;
            cnt++;
            if(curr==x){
                curr=0;
                pos++;
            }
        }
    }

    pos=0;
    curr=0;
    for(i=0;i<n;i++){
        if(pos>=weak)
            break;

        if(w[pos]>sortw[i].w){
            curr++;
            v[sortw[i].id]=true;
            cnt++;
            if(curr==x){
                curr=0;
                pos++;
            }
        }
    }
    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,greater<int>());
    sort(s,s+small,greater<int>());

    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[0];

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

    bool ok=0;

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

    if(ok)
        return -1;

    ll l=1,r=1e15*2;
    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: 0 / 10