제출 #94668

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94668		someone_aa	로봇 (IOI13_robots)	C++17	100 / 100	2254 ms	41292 KiB

robots

#include "robots.h"
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <climits>
#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];

bool check(int steps) {
    for(int i=0;i<maxn;i++) {
        cntx[i] = cnty[i] = visited[i] = 0;
    }

    int last_j = 0, reached = 0;
    priority_queue<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++) {
        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++;
        }
    }

    if(b == 0) return reached == n;

    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[]) {
    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());

    if(!check(T+1)) return -1;
    int l=0, r=T;
    int last_found = INT_MAX;
    while(l<=r) {
        int mid = (l+r)/2;
        if(check(mid)) {
            last_found = min(last_found, mid);
            r = mid-1;
        }
        else {
            l = mid+1;
        }
    }
    return last_found;
}

/*int xx[maxn], yy[maxn], ww[maxn], ss[maxn];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int a, b, n;
    cin>>a>>b>>n;
    for(int i=0;i<a;i++) cin>>xx[i];
    for(int i=0;i<b;i++) cin>>yy[i];
    for(int i=0;i<n;i++) {
        cin>>ww[i]>>ss[i];
    }
    cout<<putaway(a,b,n,xx,yy,ww,ss);
}*/

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