Submission #258335

#	Time	Username	Problem	Language	Result	Execution time	Memory
258335		eohomegrownapps	Robots (IOI13_robots)	C++14	90 / 100	350 ms	13332 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll w,h;

//map<ll,int> grid;
int indices[1000000];
ll dp[2][50001];
ll m = 1e9;
int vals[1000000];
int xcs[1000000];
int ycs[1000000];
int vtot=0;

int *xc, *yc;
int n;
bool success(ll mid){
	for (int y = 0; y<2; y++){
		for (int x = 0; x<=w; x++){
			dp[y][x]=0;
		}
	}
	for (ll i = w-1; i>=0; i--){
		dp[0][i]=mid*(w-1-i);
	}
	bool c = 1;
	int cnt = 0;
	for (ll y = h-1; y>=0; y--){
		dp[c][w]=mid*(h-1-y);
		for (ll x = w-1; x>=0; x--){
			dp[c][x]=dp[c][x+1]+dp[!c][x]-dp[!c][x+1];//-grid[x*m+y];
			while (cnt<vtot&&xcs[cnt]==x&&ycs[cnt]==y){
				dp[c][x]-=vals[cnt];
				cnt++;
			}
			if (dp[c][x]<0){
				return false;
			}
		}
		c=!c;
	}
	return true;
}

bool comp(int a, int b){
	if (yc[a]==yc[b]){
		return xc[a]>xc[b];
	} else {
		return yc[a]>yc[b];
	}
}

int putaway(int lx, int ly, int N, int xpos[], int ypos[], int xtoys[], int ytoys[]) {
	n=N;
	sort(xpos,xpos+lx);
	sort(ypos,ypos+ly);
	for (ll i = 0; i<n; i++){
		xtoys[i]=upper_bound(xpos,xpos+lx,xtoys[i])-xpos;
		ytoys[i]=upper_bound(ypos,ypos+ly,ytoys[i])-ypos;
	}
	w=lx+1;
	h=ly+1;
	xc=xtoys;yc=ytoys;
	//grid.resize(w,vector<ll>(h,0));
	/*for (ll i = 0; i<n; i++){
		grid[(xtoys[i])*m+ytoys[i]]++;
	}

	if (grid[(w-1)*m+h-1]>0){
		return -1;
	}*/
	for (int i = 0; i<n; i++){
		indices[i]=i;
	}
	sort(indices,indices+n,comp);
	int curx = xtoys[indices[0]];
	int cury = ytoys[indices[0]];
	int cnt = 0;
	for (int i = 0; i<n; i++){
		if (xtoys[indices[i]]==curx&&xtoys[indices[i]]==cury){
			cnt++;
		} else {
			xcs[vtot]=curx;
			ycs[vtot]=cury;
			vals[vtot]=cnt;
			curx=xtoys[indices[i]];
			cury=ytoys[indices[i]];
			vtot++;
			cnt=1;
		}
	}
	if (cnt>0){
		xcs[vtot]=curx;
		ycs[vtot]=cury;
		vals[vtot]=cnt;
		vtot++;
	}
	/*for (int i = 0; i<n; i++){
		cout<<xtoys[indices[i]]<<' '<<ytoys[indices[i]]<<'\n';
	}*/
	if (xtoys[indices[0]]==w-1&&ytoys[indices[0]]==h-1){
		return -1;
	}
	/*for (int i = 0; i<xcs.size(); i++){
		cout<<xcs[i]<<' '<<ytoys[i]<<' '<<vals[i]<<'\n';
	}*/
    ll l = 0, r = sqrt(n);
    while (l<=r){
    	ll mid = (l+r)/2;;
    	if (success(mid)){
    		r=mid-1;
    	} else {
    		l=mid+1;
    	}
    }
    if (l<n){
    	return l;
    }
    l = 0, r = n;
    while (l<=r){
    	ll mid = (l+r)/2;;
    	if (success(mid)){
    		r=mid-1;
    	} else {
    		l=mid+1;
    	}
    }
    return l;
}

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