Submission #123158

#	Time	Username	Problem	Language	Result	Execution time	Memory
123158		ekrem	Robots (IOI13_robots)	C++98	90 / 100	3051 ms	40096 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
#define fail(s, x...) do {fprintf(stderr, s "\n", ## x);exit(1);}while(0)
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define orta ((bas+son)/2)
#define lb lower_bound
#define mod 1000000007
#define N 2000005
using namespace std;

typedef long long ll;
typedef pair < ll , ll > ii;


ll n, m, k, x[N], y[N], kalx[N], kaly[N];
ii a[N];
set < pair < ll , ll > > :: iterator it, it2;

bool dene(ll kal){
	if(kal*(m + k) < n)
		return 0;
	set < pair < ll , ll > > xx, yy;
	priority_queue < ll > s;
	for(ll i = 1; i <= m; i++){
		kalx[i] = kal;
		xx.insert(mp(x[i], i));
	}
	for(ll i = 1; i <= k; i++){
		kaly[i] = kal;
		yy.insert(mp(y[i], i));
	}
	for(ll i = 1; i <= n; i++){
	// cout << xx.size() << " " << yy.size() << " " << s.size() << endl;
		it = xx.lb(mp(a[i].st, 0));
		if(it == xx.end()){
			it2 = yy.lb(mp(a[i].nd, 0));
			if(it2 != yy.end()){
				kaly[it2->nd]--;
				if(kaly[it2->nd] == 0)
					yy.erase(it2);
				// cout << "ikinciye doldurduk " << it2->st << " " << it2->nd << " " << kaly[it2->nd] << endl;
				continue;
			}
			if(s.empty())
				return 0;
			ll amk = -s.top();
			s.pop();
			it2 = yy.lb(mp(amk, 0));
			if(it2 == yy.end())
				return 0;
			kaly[it2->nd]--;
			if(kaly[it2->nd] == 0)
				yy.erase(it2);
			s.push(-a[i].nd);
			continue;
		}
		kalx[it->nd]--;
		if(kalx[it->nd] == 0)
			xx.erase(it);
		s.push(-a[i].nd);
		// cout << "birinciye doldurduk " << it->st << " " << it->nd << " " << kalx[it->nd] << endl;
	}
	return 1;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	n = T;m = A;k = B;
	
	for(ll i = 0; i < m; i++)
		x[i + 1] = X[i];
	sort(x + 1, x + m + 1);
	for(ll i = 0; i < k; i++)
		y[i + 1] = Y[i];
	sort(y + 1, y + k + 1);
	for(ll i = 0; i < n; i++){
		a[i + 1] = mp(W[i] + 1, S[i] + 1);
		if(W[i] + 1 > x[m] and S[i] + 1 > y[k])
			return -1;
	}
	sort(a + 1, a + n + 1);
	reverse(a + 1, a + n + 1);
	// for(ll i = 1; i <= n; i++)cout << a[i].st << " ";cout << endl;
	// for(ll i = 1; i <= n; i++)cout << a[i].nd << " ";cout << endl;
	// dene(2);
	ll bas = 1, son = n;
	while(bas < son){
		if(dene(orta))
			son = orta;
		else
			bas = orta + 1;
	}
    return orta;
}


// #define MAX_A 50000
// #define MAX_B 50000
// #define MAX_T 500000

// static ll X[MAX_A];
// static ll Y[MAX_B];
// static ll W[MAX_T];
// static ll S[MAX_T];

// int main() {
// 	freopen("out.txt", "w", stdout);
//     ll A, B, T, i;
// 	ll res;

// 	FILE *f = fopen("in.txt", "r");
// 	if (!f)
// 		fail("Failed to open input file.");

// 	res = fscanf(f, "%d", &A);
// 	if (res != 1)
// 		fail("Failed to read A from input file.");
// 	if (A < 0 || A > MAX_A)
// 		fail("A is out of bounds.");

// 	res = fscanf(f, "%d", &B);
// 	if (res != 1)
// 		fail("Failed to read B from input file.");
// 	if (B < 0 || B > MAX_B)
// 		fail("B is out of bounds.");

// 	res = fscanf(f, "%d", &T);
// 	if (res != 1)
// 		fail("Failed to read T from input file.");
// 	if (T < 1 || T > MAX_T)
// 		fail("T is out of bounds.");

// 	for (i = 0; i < A; i++) {
// 		res = fscanf(f, "%d", &X[i]);
// 		if (res != 1)
// 		    fail("Failed to read data from input file.");
//     }
// 	for (i = 0; i < B; i++) {
//         res = fscanf(f, "%d", &Y[i]);
//         if (res != 1)
//             fail("Failed to read data from input file.");
//     }
// 	for (i = 0; i < T; i++) {
//         res = fscanf(f, "%d%d", &W[i], &S[i]);
//         if (res != 2)
//             fail("Failed to read data from input file.");
//     }
// 	fclose(f);

// 	ll answer = putaway(A, B, T, X, Y, W, S);

// 	printf("%d\n", answer);

// 	return 0;
// }

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