Submission #1070273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070273		allin27x	Robots (IOI13_robots)	C++17	90 / 100	3008 ms	29644 KiB

robots

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

const int MAXT = 1e6+2;
vector<pair<int,int>> T;
int ex[MAXT];
map<int,long long> cntx, cnty;
set<pair<int,long long>> at, bt;

bool check(int a, int b, int t, int X[], int Y[], int cp) {
    for (int i=0; i<t; i++) ex[i] = 1;
    for (auto [x,cnt]: cntx) at.insert({x, cnt*cp});
    for (auto [y, cnt]: cnty) bt.insert({y, cnt*cp});
    for (int i=0; i<t; i++) {
        auto it  = bt.lower_bound({T[i].second, 1});
        if (it == bt.end()) continue;
        pair<int,int> q = *it;
        bt.erase(it); q.second--; if (q.second) bt.insert(q);
        ex[i] = 0;
    }

    for (int i=0; i<t; i++) {
        if (!ex[i]) continue;
        auto it  = at.lower_bound({T[i].first, 1});
        if (it == at.end()) return 0;
        pair<int,int> q = *it;
        at.erase(it); q.second--; if (q.second) at.insert(q);
    }


    return 1;
}

int putaway(int a, int b, int t, int X[], int Y[], int W[], int S[]){
    for (int i=0; i<t; i++) W[i]++;
    for (int i=0; i<t; i++) S[i]++;
    sort(X, X+a); sort(Y, Y+b);
    for (int i = 0; i < t; i++) T.push_back(make_pair(W[i],S[i]));
    sort(T.begin(),T.end(), greater<pair<int,int>>());

    for (int i=0; i<a; i++) cntx[X[i]] ++;
    for (int i=0; i<b; i++) cnty[Y[i]] ++;
    int l = 1, r  = t+1;
    while (l<r) {
        at.clear(); bt.clear();
        int m = (l+r)/2;
        if (check(a,b,t,X,Y,m)) r = m;
        else l = m+1;
    }
    if (l==t+1) return -1; else return l;

}

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