Submission #781058

#	Time	Username	Problem	Language	Result	Execution time	Memory
781058		tolbi	Robots (IOI13_robots)	C++17	76 / 100	117 ms	13172 KiB

robots

#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor
#define author tolbi
#include<bits/stdc++.h>
using namespace std;
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr){return os<<pr.first<<" "<<pr.second;}
template<typename X> ostream& operator<<(ostream& os, vector<X> v){for (auto &it : v) os<<it; return os;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> v){for (auto &it : v) os<<it; return os;}
#define endl '\n'
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define vint(x) vector<int> x
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define tol(bi) (1LL<<((long long)(bi)))
#define coutarr(x) for (auto &it : x) cout<<it<<endl;
typedef long long ll;
const ll INF = LONG_LONG_MAX;
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "robots.h"

int putaway(int n, int m, int t, int X[], int Y[], int W[], int S[]) {
	vector<int> x(n);
	vector<int> y(m);
	for (int i = 0; i < n; ++i)
	{
		x[i]=X[i]-1;
	}
	for (int i = 0; i < m; ++i)
	{
		y[i]=Y[i]-1;
	}
	sortarr(x);
	sortarr(y);
	vector<vector<int>> arr(n);
	vector<pair<int,int>> toys(t,{-1,-1});
	vector<int> __say(m,0);
	for (int i = 0; i < t; ++i)
	{
		auto w = lower_bound(x.begin(), x.end(), W[i]);
		auto s = lower_bound(y.begin(), y.end(), S[i]);
		if (w==x.end()) toys[i].first=-1;
		else toys[i].first=w-x.begin();
		if (s==y.end()) toys[i].second=-1;
		else toys[i].second=s-y.begin();
		if (toys[i].first==toys[i].second && toys[i].first==-1) return -1;
		if (toys[i].first==-1){
			__say[toys[i].second]++;
		}
		else {
			arr[toys[i].first].push_back(toys[i].second);
		}
	}
	auto dene = [&](int x)->bool{
		int on = 0;
		multiset<int> st;
		vector<int> say = __say;
		for (int i = n-1; i >= 0; i--){
			int mava = (n-i)*x;
			for (int j = 0; j < arr[i].size(); j++){
				on++;
				if (arr[i][j]!=-1){
					st.insert(arr[i][j]);
				}
			}
			while (on>mava && st.size()){
				auto it = st.begin();
				say[*it]++;
				on--;
				st.erase(it);
			}
			if (on>mava) return false;
		}
		on = 0;
		for (int i = m-1; i >= 0; i--){
			int mava = (m-i)*x;
			on+=say[i];
			if (on>mava) return false;
		}
		return true;
	};
	int l = 1, r = t;
	while (l<r){
		int mid = l+(r-l)/2;
		if (dene(mid)){
			r=mid;
		}
		else l=mid+1;
	}
    return l;
}

Compilation message (stderr)

robots.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
robots.cpp: In lambda function:
robots.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |    for (int j = 0; j < arr[i].size(); j++){
      |                    ~~^~~~~~~~~~~~~~~

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