Submission #123146

#	Time	Username	Problem	Language	Result	Execution time	Memory
123146		ekrem	Robots (IOI13_robots)	C++98	0 / 100	464 ms	13460 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 < int , int > ii;


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

bool dene(int kal){
	if(kal*(m + k) < n)
		return 0;
	set < ii > xx;
	if(!m)
		assert(0);
	for(int i = 1; i <= m; i++){
		kalx[i] = kal;
		xx.insert(mp(x[i], i));
	}
	for(int i = 1; i <= n; i++){
	// cout << xx.size() << " " << yy.size() << " " << s.size() << endl;
		it = xx.lb(mp(a[i].st, 0));
		if(xx.empty() or it == xx.end())
			return 0;
		kalx[it->nd]--;
		if(kalx[it->nd] == 0)
			xx.erase(*it);
		// 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(int i = 0; i < m; i++)
		x[i + 1] = X[i];
	sort(x + 1, x + m + 1);
	for(int i = 0; i < k; i++)
		y[i + 1] = Y[i];
	sort(y + 1, y + k + 1);
	for(int 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(int i = 1; i <= n; i++)cout << a[i].st << " ";cout << endl;
	// for(int i = 1; i <= n; i++)cout << a[i].nd << " ";cout << endl;
	// dene(2);
	int 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 int X[MAX_A];
// static int Y[MAX_B];
// static int W[MAX_T];
// static int S[MAX_T];

// int main() {
// 	freopen("out.txt", "w", stdout);
//     int A, B, T, i;
// 	int 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);

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

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

// 	return 0;
// }

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