Submission #839041

#	Time	Username	Problem	Language	Result	Execution time	Memory
839041		Cookie	Robots (IOI13_robots)	C++14	100 / 100	1729 ms	23736 KiB

robots

#include<bits/stdc++.h>
#include "robots.h"
using namespace std;
ifstream fin("susss.txt");
ofstream fout("res.txt");
#define forr(i, a, b) for(int i = a; i < b; i++)
#define pb push_back
#define vt vector
#define fi first
#define se second
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define sz(v) (int)v.size()
const int mxn = 1e6, inf = 1e9, mod = 1e9 + 7, mxm = 50005;
int t, a, b;
pii p[mxn + 1];
int x[mxm + 1], y[mxm + 1], cnt[mxm + 1];
bool good[mxn + 1];
bool ck(int mid){
    set<pair<int, int>>s;
    for(int i = 1; i <= b; i++){
        cnt[i] = mid; s.insert(make_pair(y[i], i));
    }
    for(int i = t; i >= 1; i--){
        good[i] = 0;
        auto it = s.lower_bound(make_pair(p[i].se + 1, -1));
        if(it != s.end()){
            good[i] = 1;
            int id = (*it).second;
            cnt[id]--;
            if(cnt[id] == 0){
                s.erase(make_pair(y[id], id));
            }
        }
    }
    int bestid = a, cntt = mid;
    for(int i = t; i >= 1; i--){
        if(!good[i]){
            if(p[i].fi >= x[bestid])return(0);
            cntt--;
            if(cntt == 0){
                bestid--; cntt = mid;
            }
        }
    }
    return(1);
}

int putaway(int A,int B,int T, int X[],int Y[],int W[],int S[]){
    a = A; b = B; t = T; 
    for(int i = 1; i <= a; i++)x[i] = X[i - 1];
    for(int i = 1; i <= b; i++)y[i] = Y[i - 1];
    sort(x + 1, x + a + 1); sort(y + 1, y + b + 1);
    for(int i = 1; i <= t; i++){
        p[i].fi = W[i - 1]; p[i].se = S[i - 1];
    }
    sort(p + 1, p + t + 1);
    int l = 1, r = t, ans = -1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(ck(mid)){
            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: 10 / 10