Submission #1214279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214279		Malix	Robots (IOI13_robots)	C++20	100 / 100	480 ms	17728 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) x.begin(),x.end()

ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

vector<pi> a;
vi b;
set<pi> d;
int x,y,n;

bool solve(int m){
    set<pi> c=d;
    vi Y(y,m);
    int pos=0;
    priority_queue<int,vi,greater<int>> st;
    REP(i,0,x){
        while(pos<n&&a[pos].F>=b[i]){
            st.push(a[pos].S);
            auto it=c.upper_bound({st.top(),y});
            if(it==c.end())return 0;
            int ps=it->S;
            Y[ps]--;
            if(Y[ps]==0)c.erase(it);
            st.pop();
            pos++;
        }
        int cn=m;
        while(pos<n&&cn--)st.push(a[pos++].S);
        if(pos==n)break;
    }
    while(pos<n&&!c.empty()){
        st.push(a[pos].S);
        auto it=c.upper_bound({st.top(),y});
        if(it==c.end())return 0;
        int ps=it->S;
        Y[ps]--;
        if(Y[ps]==0)c.erase(it);
        st.pop();
        pos++;
    }
    return pos==n;
}

int BS(int l,int r){
    if(l==r)return l;
    int m=(l+r)/2;
    if(solve(m))return BS(l,m);
    else return BS(m+1,r);
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    n=T;x=A;y=B;
    a.resize(n);b.resize(x);
    REP(i,0,n)a[i]={W[i],S[i]};
    REP(i,0,x)b[i]=X[i];
    REP(i,0,y)d.insert({Y[i],i});
    sort(all(a));sort(all(b));
    reverse(all(a));reverse(all(b));
    int ans=BS(1,1000001);
    if(ans==1000001)return -1;
    else return ans;
}

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