oj.uz

Submission #17226

# Submission time Handle Problem Language Result Execution time Memory
17226 2015-11-09T09:07:41 Z erdemkiraz Robots (IOI13_robots) C++
76 / 100
 3000 ms 24012 KB 
#include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

#include "robots.h"

const int N = 1e6 + 5;

int n;
int A, B;
int X[N], Y[N];
ii a[N];
multiset < ii > s;
vector < int > v;

bool f(int x) {
	s.clear();
	v.clear();
	for(int i = 0; i < A; i++)
		s.insert(ii(X[i], x));
	for(int i = n - 1; i >= 0; i--) {
		type(s) it = s.lower_bound(ii(a[i].first + 1, 0));
		if(it != s.end()) {
			int st = it -> first;
			int nd = it -> second;
			s.erase(it);
			if(nd - 1)
				s.insert(ii(st, nd - 1));
		}
		else {
			v.push_back(a[i].second);
		}
	}
	int ptr = 0;
	for(int i = B - 1; i >= 0; i--) {
		int rem = x;
		while(ptr < v.size() and rem and Y[i] > v[ptr]) {
			rem--;
			ptr++;
		}
	}
	return ptr == v.size();
}

int putaway(int A, int B, int n, int X[], int Y[], int W[], int S[]) {
	:: n = n;
	:: A = A;
	:: B = B;
	sort(X, X + A);
	sort(Y, Y + B);
	for(int i = 0; i < A; i++)
		:: X[i] = X[i];
	for(int i = 0; i < B; i++)
		:: Y[i] = Y[i];
	for(int i = 0; i < n; i++) {
		a[i] = ii(S[i], W[i]);
	}
	sort(a, a + n);
	for(int i = 0; i < n; i++)
		swap(a[i].first, a[i].second);
	if(!f(n))
		return -1;
	int l = 1, r = n;
	while(l < r) {
		int m = l + r >> 1;
		if(f(m))
			r = m;
		else
			l = m + 1;
	}
	return l;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21652 KB Output is correct
2 Correct 0 ms 21652 KB Output is correct
3 Correct 0 ms 21652 KB Output is correct
4 Correct 3 ms 21652 KB Output is correct
5 Correct 0 ms 21652 KB Output is correct
6 Correct 0 ms 21652 KB Output is correct
7 Correct 0 ms 21652 KB Output is correct

Subtask #2
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21652 KB Output is correct
2 Correct 3 ms 21652 KB Output is correct
3 Correct 3 ms 21652 KB Output is correct
4 Correct 2830 ms 24012 KB Output is correct
5 Correct 361 ms 23896 KB Output is correct
6 Correct 681 ms 23896 KB Output is correct
7 Execution timed out 3000 ms 23892 KB Program timed out
8 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21652 KB Output is correct
2 Correct 3 ms 21652 KB Output is correct
3 Correct 0 ms 21652 KB Output is correct
4 Correct 3 ms 21652 KB Output is correct
5 Correct 0 ms 21652 KB Output is correct
6 Correct 0 ms 21652 KB Output is correct
7 Correct 0 ms 21652 KB Output is correct
8 Correct 3 ms 21652 KB Output is correct
9 Correct 0 ms 21652 KB Output is correct
10 Correct 3 ms 21652 KB Output is correct
11 Correct 0 ms 21652 KB Output is correct
12 Correct 0 ms 21652 KB Output is correct
13 Correct 0 ms 21652 KB Output is correct
14 Correct 0 ms 21652 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21652 KB Output is correct
2 Correct 0 ms 21652 KB Output is correct
3 Correct 3 ms 21652 KB Output is correct
4 Correct 3 ms 21652 KB Output is correct
5 Correct 0 ms 21652 KB Output is correct
6 Correct 0 ms 21652 KB Output is correct
7 Correct 3 ms 21652 KB Output is correct
8 Correct 0 ms 21652 KB Output is correct
9 Correct 0 ms 21652 KB Output is correct
10 Correct 0 ms 21652 KB Output is correct
11 Correct 3 ms 21652 KB Output is correct
12 Correct 3 ms 21652 KB Output is correct
13 Correct 0 ms 21652 KB Output is correct
14 Correct 0 ms 21652 KB Output is correct
15 Correct 3 ms 21652 KB Output is correct
16 Correct 36 ms 21652 KB Output is correct
17 Correct 33 ms 21652 KB Output is correct
18 Correct 21 ms 21652 KB Output is correct

Subtask #5
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 21652 KB Output is correct
2 Correct 0 ms 21652 KB Output is correct
3 Correct 0 ms 21652 KB Output is correct
4 Correct 0 ms 21652 KB Output is correct
5 Correct 3 ms 21652 KB Output is correct
6 Correct 0 ms 21652 KB Output is correct
7 Correct 3 ms 21652 KB Output is correct
8 Correct 0 ms 21652 KB Output is correct
9 Correct 3 ms 21652 KB Output is correct
10 Correct 2906 ms 24012 KB Output is correct
11 Correct 364 ms 23896 KB Output is correct
12 Correct 679 ms 23896 KB Output is correct
13 Execution timed out 3000 ms 23892 KB Program timed out
14 Halted 0 ms 0 KB -