제출 #1166226

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166226		sano	Robots (IOI13_robots)	C++20	100 / 100	2382 ms	17132 KiB

robots

#include "robots.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#define shit short int
#define ll long long
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define NEK 2000000000
#define mod 998244353
#define mod2 1000000009
#define rsz resize 
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define sig 0.0000001

using namespace std;

bool check(int a, int b, int t, int *x, int *y, vec<pii> v, int mid) {
	unordered_map<int, int> umap;
	set<int> s;
	For(i, b) {
		umap[y[i]] += mid;
		s.insert(y[i]);
	}
	rfor(i, t - 1) {
		auto poz = s.upper_bound(v[i].ss);
		if (poz == s.end()) { continue; }
		umap[*poz]--;
		if (umap[*poz] == 0) s.erase(poz);
		swap(v.back(), v[i]);
		v.pop_back();
	}
	sort(v.begin(), v.end());
	int mam = mid;
	int som = a - 1;
	while (som >= 0) {
		if (v.empty()) return 1;
		if (v.back().ff >= x[som]) return 0;
		v.pop_back(); mam--;
		if (mam == 0) {
			mam = mid;
			som--;
		}
	}
	if (v.empty()) return 1;
	return 0;
}

int putaway(int a, int b, int t, int x[], int y[], int w1[], int s1[]) {
	vec<pii> v;
	For(i, t) v.push_back({ w1[i], s1[i] });
	sort(x, x + a);
	sort(v.begin(), v.end());
	int l = 1, r = t;
	while (l < r) {
		int mid = (l + r) / 2;
		if (check(a, b, t, x, y, v, mid)) r = mid;
		else l = mid + 1;
	}
	if (!check(a, b, t, x, y, v, l)) return -1;
	return l;
}
/*
signed main() {
	ll t;
	//cin >> t;
	t = 1;
	For(ww, t) {
		int a, b, t;
		cin >> a >> b >> t;
		int x[10], y[10], w[10], s[10];
		For(i, a) cin >> x[i];
		For(i, b) cin >> y[i];
		For(i, t) cin >> w[i] >> s[i];
		cout << putaway(a, b, t, x, y, w, s) << '\n';
	}
	return 0;
}*/

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