Submission #31454

#	Time	Username	Problem	Language	Result	Execution time	Memory
31454		top34051	Robots (IOI13_robots)	C++14	0 / 100	6 ms	19404 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
using namespace std;

struct node {
    int id,x,y;
    node(int _id = 0,int _x = 0,int _y = 0) {
        id = _id; x = _x; y = _y;
    }
};

int n,m,k;
int a[50005], b[50005];
bool ok[1000005];
node p[1000005];
map<int,int> mp;

bool cmpx(node x,node y) {
    return x.x>y.x;
}

bool cmpy(node x,node y) {
    return x.y>y.y;
}

bool check(int cnt) {
    int i;
    map<int,int>::iterator it;
    memset(ok,0,sizeof(ok));
    mp.clear();
    for(i=0;i<n;i++) mp[a[i]] += cnt;
    sort(&p[0],&p[k],cmpy);
    for(i=0;i<k;i++) {
        it = mp.lower_bound(p[i].x);
        if(it==mp.end()) continue;
        it->second--;
        if(it->second==0) mp.erase(it);
        ok[p[i].id] = 1;
    }
    mp.clear();
    for(i=0;i<m;i++) mp[b[i]] += cnt;
    sort(&p[0],&p[k],cmpx);
    for(i=0;i<k;i++) {
        if(ok[p[i].id]) continue;
        it = mp.lower_bound(p[i].y);
        if(it==mp.end()) continue;
        it->second--;
        if(it->second==0) mp.erase(it);
        ok[p[i].id] = 1;
    }
    for(i=0;i<k;i++) if(!ok[i]) return 0;
    return 1;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    int i,l,r,mid,ans;
    n = A; m = B; k = T;
    for(i=0;i<n;i++) a[i] = X[i];
    for(i=0;i<m;i++) b[i] = Y[i];
    for(i=0;i<k;i++) p[i] = node(i,W[i],S[i]);
    l = 0; r = k; ans = -1;
    while(l<=r) {
        mid = (l+r)/2;
        if(check(mid)) {
            ans = mid;
            r = mid-1;
        }
        else l = mid+1;
    }
    return ans;
}

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