Submission #619928

#	Time	Username	Problem	Language	Result	Execution time	Memory
619928		M_W	Robots (IOI13_robots)	C++17	100 / 100	2544 ms	43048 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
#define ii pair<int, int>
#define ar array<int, 3>
using namespace std;
bitset<1000001> mark;
vector<ii> v, item_w, item_s;

struct cmp{
	bool operator() (const ar &a, const ar &b) const{
		return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
	}
};

bool check(int mid, int T, int X[], int Y[], int W[], int S[]){
	for(int i = 0; i <= T; i++) mark[i] = 0;
	priority_queue<ar, vector<ar>, cmp> wt, sz;
	int idx_w = 0, idx_s = 0;
	
	// printf("T = %d\n", mid);
	for(auto [x, t] : v){
		int cnt = 0;
		if(t == 1){
			while(idx_w < T && item_w[idx_w].first < x){
				wt.push({item_w[idx_w].first, S[item_w[idx_w].second], item_w[idx_w].second});
				idx_w++;
			}
			while(!wt.empty()){
				auto [w, s, i] = wt.top();
				if(w >= x || cnt >= mid) break;
				wt.pop();
				
				if(mark[i]) continue; 
				mark[i] = 1;
				
				// printf("bot weak %d take %d (%d)\n", x, w, i);
				cnt++;
			}
		}
		else{
			while(idx_s < T && item_s[idx_s].first < x){
				sz.push({item_s[idx_s].first, W[item_s[idx_s].second], item_s[idx_s].second});
				idx_s++;
			}
			while(!sz.empty()){
				auto [s, w, i] = sz.top();
				if(s >= x || cnt >= mid) break;
				
				sz.pop();
				if(mark[i]) continue; 
				mark[i] = 1;
				
				// printf("bot small %d take %d (%d)\n", x, s, i);
				cnt++;
			}
		}
	}
	
	while(idx_w < T){
		wt.push({item_w[idx_w].first, S[item_w[idx_w].second], item_w[idx_w].second});
		idx_w++;
	}
	while(idx_s < T){
		sz.push({item_s[idx_s].first, W[item_s[idx_s].second], item_s[idx_s].second});
		idx_s++;
	}
	while(!sz.empty() && mark[sz.top()[2]]) sz.pop();
	while(!wt.empty() && mark[wt.top()[2]]) wt.pop();
	
	// printf(">> %d %d\n", sz.size(), wt.size());
	
	return sz.empty() && wt.empty();
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    for(int i = 0; i < A; i++) v.push_back({X[i], 1});
    for(int i = 0; i < B; i++) v.push_back({Y[i], 2});
    sort(v.begin(), v.end());
    
    for(int i = 0; i < T; i++){
		item_w.push_back({W[i], i});
		item_s.push_back({S[i], i});
	}
	sort(item_w.begin(), item_w.end());
	sort(item_s.begin(), item_s.end());
	
	int l = 1, r = T; bool ans = false;
    while(l < r){
    	int mid = (l + r) >> 1;
		if(check(mid, T, X, Y, W, S)){
			ans = true;
			r = mid;
		}
		else l = mid + 1;
	}
	if(check(l, T, X, Y, W, S)) ans = true;
	
	if(!ans) return -1;
	return l;
}

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