Submission #200497

#	Time	Username	Problem	Language	Result	Execution time	Memory
200497		liwi	Robots (IOI13_robots)	C++14	39 / 100	3096 ms	23032 KiB

robots

#include "robots.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef gp_hash_table<int, null_type,hash<int>, equal_to<int>, direct_mask_range_hashing<int>, linear_probe_fn<>,
    hash_standard_resize_policy<hash_exponential_size_policy<>, hash_load_check_resize_trigger<true>,true>> hash_set;
typedef gp_hash_table<int,null_type> hash_map;

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define all(a) a.begin(),a.end()
#define println printf("\n");
#define readln(x) getline(cin,x);
#define pb push_back
#define endl "\n"
#define INT_INF 0x3f3f3f3f
#define LL_INF 0x3f3f3f3f3f3f3f3f
#define EPS 1e-9
#define MOD 1000000007
#define MOD2 1494318097
#define SEED 131
#define mp make_pair
#define fastio cin.tie(0); cin.sync_with_stdio(0);

#define MAXN 50005
#define MAXT 1000005

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef pair<int,pii> triple;
typedef int8_t byte;

const ld PI = (ld)4*atanl(1);

mt19937 g1(chrono::steady_clock::now().time_since_epoch().count());

int randint(int a, int b){return uniform_int_distribution<int>(a, b)(g1);}
ll randlong(ll a,ll b){return uniform_int_distribution<long long>(a, b)(g1);}

ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
ll fpow(ll  b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}

int num_weak,num_small,num_toys;
int weak[MAXN],small[MAXN];
bool done[MAXT];
pii arr[MAXT];
set<pii> s;

inline bool cmp(pii a, pii b){
    if(a.first == b.first) return a.second>b.second;
    return a.first<b.first;
}

inline bool works(int mid){
    memset(done,false,sizeof done);
    s.clear();
    for(int i=1; i<=num_weak; i++)
        s.insert(mp(weak[i],mid));
    for(int i=num_toys; i>=1; i--){
        auto it = s.upper_bound(mp(arr[i].second,INT_MAX));
        if(it == s.end()) continue;
        done[i] = true;
        pii t = *it;
        s.erase(t);
        if(t.second > 1)
            s.insert(mp(t.first,t.second-1));
    }
    int ptr = num_toys;
    for(int i=num_small; i>=1; i--){
        for(int k=1; k<=mid; k++){
            while(ptr >= 1 && done[ptr]) ptr--;
            if(ptr == 0) return true;
            if(arr[ptr].first >= small[i]) return false;
            ptr--;
        }
    }
    while(ptr >= 1 && done[ptr]) ptr--;
    return ptr==0;
}

inline bool can(int mid){
    if(works(mid)) return true;
    swap(num_small,num_weak);
    swap(small,weak);
    for(int i=1; i<=num_toys; i++)
        swap(arr[i].first,arr[i].second);
    return works(mid);
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]){
    num_weak = A, num_small = B, num_toys = T;
    for(int i=1; i<=A; i++) weak[i] = X[i-1];
    for(int i=1; i<=B; i++) small[i] = Y[i-1];
    sort(weak+1,weak+num_weak+1);
    sort(small+1,small+num_small+1);
    for(int i=1; i<=num_toys; i++){
        arr[i].second = W[i-1], arr[i].first = S[i-1];
        if(arr[i].second >= weak[num_weak] && arr[i].first >= small[num_small])
            return -1;
    }
    sort(arr+1,arr+num_toys+1,cmp);
    int low = 0, high = num_toys, ans = num_toys;
    while(low <= high){
        int mid = (low+high)/2;
        if(can(mid)){
            ans = mid;
            high = mid-1;
        }else low = mid+1;
    }
    return ans;
}

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