Submission #933406

#	Time	Username	Problem	Language	Result	Execution time	Memory
933406		PoPularPlusPlus	Robots (IOI13_robots)	C++17	100 / 100	2287 ms	31996 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define vf first 
#define vs second
const int mod = 1000000007;
 
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
 
int putaway(int n,int m, int t,
int weak[],int small[], int w[] ,int s[]){
	int l = 1 , r = t;
	vector<pair<int,int>> v;
	for(int i = 0; i < t; i++){
		v.pb(mp(s[i],w[i]));
	}
	sort(all(v));
	sort(small,small+m);
	sort(weak,weak+n);
	int ans = -1;
	while(l <= r){
		int mid = (l + r)/2;
		priority_queue<pair<int,int>> pq;
		int j = 0;
		for(int i = 0; i < m; i++){
			while(j < t && v[j].vf < small[i]){
				pq.push(mp(v[j].vs,v[j].vf));
				j++;
			}
			int cnt = 0;
			while(cnt < mid && pq.size()){
				pq.pop();
				cnt++;
			}
		}
		while(j < t){
			pq.push(mp(v[j].vs,v[j].vf));
			j++;
		}
		vector<pair<int,int>> elements;
		while(pq.size()){
			elements.pb(pq.top());
			pq.pop();
		}
		for(auto it :elements){
			pq.push(it);
		}
		for(int i = n - 1; i >= 0; i--){
			int cnt = 0;
			while(cnt < mid && pq.size() && pq.top().vf < weak[i]){
				cnt++;
				pq.pop();
			}
		}
		if(pq.size() == 0){
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	return ans;
}
 
void solve(){
	/*int n , m , t;
	cin >> n >> m >> t;
	int weak[n] , small[m];
	for(int i = 0; i < n; i++)
		cin >> weak[i];
	for(int i = 0; i < m; i++)
		cin >> small[i];
	int w[t],s[t];
	for(int i = 0; i < t; i++)
		cin >> w[i] >> s[i];
	cout << ans << "\n";*/
}
/*
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//int t;cin>>t;
	//while(t--)
		solve();
	return 0;
}*/

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