Submission #478225

#	Time	Username	Problem	Language	Result	Execution time	Memory
478225		joshjms	Robots (IOI13_robots)	C++14	Compilation error	0 ms	0 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
 
#define ll long long
#define ld long double
#define int long long
#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 = INFF;
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.lower_bound({toys[i].se, 0});
		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 = min(ans, md);
		else l = md + 1;
	}
	return ans;
}

// void solve(){
// 	cin >> a >> b >> t;
// 	for(int i = 0; i < a; i++)
// 		cin >> x[i];
// 	for(int i = 0; i < b; i++)
// 		cin >> y[i];
// 	for(int i = 0; i < t; i++)
// 		cin >> toys[i].fi >> toys[i].se;
// 	sort(toys, toys + t);
// 	sort(x, x + a);
// 	sort(y, y + b);
// 	l = 1, r = t;
// 	while(l <= r){
// 		md = (l + r) / 2;
// 		if(check())
// 			r = md - 1, ans = min(ans, md);
// 		else l = md + 1;
// 	}
// 	cout << ans << "\n";
// }

// signed main(){
// 	konaqua;
// 	solve();
// 	otsuaqua;
// }

/*
3 2 10
6 2 9
4 7
4 6
8 5
2 3
7 9
1 8
5 1
3 3
8 7
7 6
10 5
*/

Compilation message (stderr)

/usr/bin/ld: /tmp/ccSJJXU8.o: in function `main':
grader.c:(.text.startup+0x1b1): undefined reference to `putaway'
collect2: error: ld returned 1 exit status