Submission #64949

#	Time	Username	Problem	Language	Result	Execution time	Memory
64949		someone_aa	Robots (IOI13_robots)	C++17	0 / 100	16 ms	9524 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 1000100;
vector<pair<int, pair<int,int> > > w;
vector<pair<int,int> > s;
int a, b, n, x[maxn], y[maxn];
int cntx[maxn], cnty[maxn];
bool visited[maxn];

void preprocess(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    a = A, b = B, n = T;
    for(int i=0;i<T;i++) {
        w.pb(mp(W[i], mp(S[i], i)));
        s.pb(mp(S[i], i));
    }
    sort(w.begin(), w.end());
    for(int i=0;i<A;i++) x[i] = X[i];
    for(int i=0;i<B;i++) y[i] = Y[i];
    sort(x, x+A);
    sort(y, y+B);
    sort(s.begin(), s.end());
}

bool check(int steps) {
    memset(cntx, 0, sizeof(cntx));
    memset(cnty, 0, sizeof(cnty));
    memset(visited,false,sizeof(visited));

    int last_j = 0, reached = 0;
    priority_queue<pair<int,int>, vector<pair<int,int> > > pq;

    /*for(int i=0;i<n;i++) {
        cout<<w[i].first<<" "<<w[i].second.first<<" "<<w[i].second.second<<"\n";
    }*/

    for(int i=0;i<a;i++) {
        // dodadi gi tija sto gi sobira
        for(int j=last_j;j<n && w[j].first <= x[i];j++) {
            pq.push(mp(w[j].second.first, w[j].second.second));
            last_j = j + 1;
        }

        //cout<<i<<": "<<pq.size()<<"\n";

        while(!pq.empty() && cntx[i] < steps) {
            int last_ind = pq.top().second;
            //cout<<"Deleting: "<<pq.top().first<<" "<<pq.top().second<<"\n";
            visited[last_ind] = true;
            pq.pop();
            cntx[i]++;
            reached++;
        }
    }

    int curry = 0;
    s.pb(mp(0,0));
    for(int i=0;i<n && curry<b;i++) {
        if(visited[s[i].second]) continue;

        while((s[i].first > y[curry] || cnty[curry] == steps) && curry < b) curry++;
        if(curry == b) break;
        if(s[i].first <= y[curry]) {
            visited[s[i].second] = true;
            reached++;
            cnty[curry] ++;
        }
    }
    return reached == n;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    preprocess(A,B,T,X,Y,W,S);

    if(!check(T+1)) return -1;
    int index=T;
    for(int cekor=T/2;cekor>0;cekor/=2) {
        while(index-cekor>=0 && check(index-cekor)) index-=cekor;
    }
    return index;
}

/*int main() {
    int a=3, b=2, t=10;
    int x[3] = {6, 2, 9};
    int y[2] = {4, 7};
    int w[10] = {4,8,2,7,1,5,3,8,7,10};
    int s[10] = {6,5,3,9,8,1,3,7,6,5};

    cout<<putaway(a, b, t, x, y, w, s);

}*/

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