Submission #539102

#	Time	Username	Problem	Language	Result	Execution time	Memory
539102		myrcella	Robots (IOI13_robots)	C++17	100 / 100	2720 ms	29108 KiB

robots

//by szh
#include "robots.h"
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}


vector <pii> item;
vector <pii> rest;

const int maxn = 1e6+10;
int w[maxn],s[maxn];
int cnt[maxn];
int AA,BB;

bool check(int x) {
//	debug(x);
	set <pii> robot;
	while (!rest.empty()) rest.pop_back();
	rep(i,0,BB) robot.insert({s[i],i}),cnt[i] = x;
	for (int i=0;i<SZ(item);i++) {
		auto it = robot.upper_bound({item[i].se,mod});
		if (it == robot.end()) rest.pb(item[i]);
		else {
			pii cur = *it;
			cnt[cur.se]--;
			if (cnt[cur.se]==0) robot.erase(cur);
		}
	}
	robot.clear();
	rep (i,0,AA) robot.insert({w[i],i}),cnt[i] = x;
	for (int i=0;i<SZ(rest);i++) {
		auto it = robot.upper_bound({rest[i].fi,mod});
//		debug(rest[i].fi);
		if (it == robot.end()) return false;
		else {
			pii cur = *it;
//			debug(cur.fi);
			cnt[cur.se]--;
			if (cnt[cur.se]==0) robot.erase(cur);
		}
	}
	return true;
}

bool cmp (pii a, pii b ) {
	if (a.fi==b.fi) return a<b;
	else return a.fi>b.fi;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	AA=A,BB=B;
	rep(i,0,T) item.pb({W[i],S[i]});
	sort(X,X+A);
	sort(Y,Y+B);
	rep(i,0,A) w[i] = X[i];
	rep(i,0,B) s[i] = Y[i];
	sort(ALL(item),cmp);
	if (!check(T)) return -1;
	int l = 1,r = T;
	while (l<r) {
		int mid=l+r>>1;
		if (check(mid)) r = mid;
		else l = mid+1;
	}
    return l;
}
/*
int main() {
	int tmp1[] = {5,7};
	int tmp2[] = {};
	int tmp3[] = {1,7};
	int tmp4[] = {};
	cout<<putaway(2,0,2, tmp1, tmp2, tmp3,tmp4);
}
*/

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:80:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |   int mid=l+r>>1;
      |           ~^~

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