Submission #478235

#	Time	Username	Problem	Language	Result	Execution time	Memory
478235		joshjms	Robots (IOI13_robots)	C++14	100 / 100	2333 ms	24400 KiB

robots

#include "robots.h"

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define konaqua ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define otsuaqua exit(0);
 
#define debug(x) cout << #x << " => " << x << "\n"
#define all(x) x.begin(), x.end()
#define sp " "
 
/*
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/
 
const ll INFF = 1e18 + 5;
const ll INF = 1e10 + 5;
const int MX = 1e6 + 5;
const int MXL = 105;
const int mod = 1e9 + 7;
const double ERROR = 1e-8;

const ld pi = 3.14159265358979323846;
 
const int set_inf = 0x3f3f3f3f;

int a, b, t;

int l, r, md, ans = -1;
pair <int,int> toys[1000005];
int x[50005], y[50005];

set <pair<int,int>> st;
bool vis[1000005];
int sr[50005], wr[50005], it;

bool check(){
	memset(vis, 0, sizeof(vis));
	memset(wr, 0, sizeof(wr));
	memset(sr, 0, sizeof(sr));
	st.clear();
	for(int i = 0; i < b; i++)
		st.insert({y[i], i});
	for(int i = t - 1; i >= 0; i--){
		if(st.empty()) break;
		auto idx = st.upper_bound({toys[i].se, 1e9 + 7});
		if(idx == st.end()) continue;
		pair <int,int> p = *idx;
		vis[i] = 1;
		sr[p.se]++;
		if(sr[p.se] >= md) st.erase(idx);
	}
	it = 0;
	for(int i = 0; i < t; i++){
		if(vis[i]) continue;
		while((toys[i].fi >= x[it] || wr[it] >= md) && it < a) it++;
		if(it >= a) break;
		vis[i] = 1;
		wr[it]++;
	}
	for(int i = 0; i < t; i++){
		if(!vis[i]) return 0;
	}
	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 = 0; i < t; i++)
		toys[i] = make_pair(W[i], S[i]);
	sort(toys, toys + t);
	for(int i = 0; i < a; i++)
		x[i] = X[i];
	sort(x, x + a);
	for(int i = 0; i < b; i++)
		y[i] = Y[i];
	sort(y, y + b);
	l = 1, r = t;
	while(l <= r){
		md = (l + r) / 2;
		if(check()){
			r = md - 1, ans = md;
		}
		else l = md + 1;
	}
	return ans;
}

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