Submission #370982

#	Time	Username	Problem	Language	Result	Execution time	Memory
370982		shivensinha4	Robots (IOI13_robots)	C++17	14 / 100	1211 ms	19300 KiB

robots

#include "bits/stdc++.h"
#include"robots.h"
#ifdef mlocal
#include "grader.c"
#endif
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
//#define endl '\n'

// Ask for sum 1 -> n for full (one based indexing)
class BIT {
	private: vector<ll> tree; int n = 1e6;
	int LSOne(int x) {
		return x&(-x);
	}

	public:
		void build(int x) {
			n = x;
			tree.resize(n+1);
		}
		ll sum(int a) {
			ll sum = 0;
			for (; a > 0; a -= LSOne(a)) sum += tree[a];
			return sum;
		}
		ll sum(int a, int b) {
			return sum(b) - (a == 1 ? 0 : sum(a-1));
		}
		void update(int p, ll v) {
			for (; p < n+1; p += LSOne(p)) tree[p] += v;
		}
};

int a, b, t;
vi wlim, slim;
vector<ii> toys, toys2;
BIT tree;

bool check(ll box) {
	vi left, done;
	
	for (int i = t-1; i >= 0; i--) {
		int pt = lower_bound(slim.begin(), slim.end(), toys[i][1]) - slim.begin();
		if (pt < b and tree.sum(pt+1, b) < box * (b-pt)) {
			tree.update(pt+1, 1);
			done.push_back(pt);
		} else left.push_back(i);
	}
	
	for (auto &i: done) tree.update(i+1, -1);
	done.clear();
	
	bool valid = true;
	
	for (auto i: left) {
		int pt = lower_bound(wlim.begin(), wlim.end(), toys[i][0]) - wlim.begin();
		if (pt < a and tree.sum(pt+1, a) < box * (a-pt)) {
			tree.update(pt+1, 1);
			done.push_back(pt);
		} else {
			valid = false;
			break;
		}
	}
	
	for (auto &i: done) tree.update(i+1, -1);
	
	return valid;
}

bool checkk(ll box) {
	bool valid = check(box);
	if (!valid) {
		swap(toys2, toys);
		swap(a, b);
		swap(wlim, slim);
		valid |= check(box);
		swap(toys2, toys);
		swap(a, b);
		swap(wlim, slim);
	}
	return valid;
}


int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    a = A, b = B, t = T;
	wlim.reserve(A); slim.reserve(B); toys.reserve(T);
    for_(i, 0, a) {
		wlim.push_back(X[i]);
		wlim[i] -= 1;
    }
	for_(i, 0, b) {
		slim.push_back(Y[i]);
		slim[i] -= 1;
    }
	for_(i, 0, t) toys.push_back({W[i], S[i]});
	toys2 = toys;
	for_(i, 0, t) swap(toys2[i][0], toys2[i][1]);
	sort(wlim.begin(), wlim.end());
	sort(slim.begin(), slim.end());
	sort(toys.begin(), toys.end());
	sort(toys2.begin(), toys2.end());
	
	for_(i, 0, t) if ((a == 0 or toys[i][0] > wlim.back()) and (b == 0 or toys[i][1] > slim.back())) return -1;
	
	tree.build(max(a, b));
	int l = 0, r = T+1, ans = r;
	while (l < r) {
		int mid = (l+r)/2;
		bool fin = checkk(mid);
		if (fin) {
			ans = r = mid;
		} else l = mid+1;
	}
	
	return ans;
}

//#define MAX_A 50000
//#define MAX_B 50000
//#define MAX_T 500000
//#define fail(s, x...) do { \
//		fprintf(stderr, s "\n", ## x); \
//		exit(1); \
//	} while(0)
//
//static int X[MAX_A];
//static int Y[MAX_B];
//static int W[MAX_T];
//static int S[MAX_T];
//
//int main() {
//    int A, B, T, i;
//	int res;
//
//	FILE *f = fopen("test.in", "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;
//}

Compilation message (stderr)

robots.cpp:128:1: warning: multi-line comment [-Wcomment]
  128 | //#define fail(s, x...) do { \
      | ^

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