2014-04-19 - HIR180's diary

■ IOI 2013 Robots 00:57

考えたこと:

weak robotsから処理しよう->

明らかにsizeがでかいほうからやったらうれしい->

"sizeが大きい順にみて、取れるなら最も重さlimitが厳しいやつでとる"

というGreedy?->

通った。

なんでこれでいいのかはわからない。たぶんkruskal法が正しく動くのと同じ理由(?)で正しく動くのだと思う。


#include 
#include 
#include 
#include 
using namespace std;
int x[50005],y[50005],w[1000005],s[1000005],pre[1000005];
int n,m,t;
struct mat
{
    int g,sz;
    bool operator < (const mat& x) const
    {
        return sz > x.sz;
    }
};
//weak -> small
void sol()
{
	int lb=0,ub=t+1;
	sort(x,x+n);
	sort(w,w+t);
    	while(ub-lb > 1)
    	{
    		int mid=(lb+ub)>>1;
    		bool ok=true;
    		if(1LL*n*mid < t)
	        {
	            ok=false; goto fail;
	        }
    		for(int i=0;iif(w[t-1-i] > x[n-1-(i/mid)]) { ok=false; break; }
	        }
	        fail:;
	        if(ok) ub=mid;
	        else lb=mid;
    	}
    	printf("%d\n",ub==t+1?-1:ub);
}
int main()
{
    scanf("%d %d %d",&n,&m,&t);
    for(int i=0;i"%d",&x[i]);
    for(int i=0;i"%d",&y[i]);
    for(int i=0;i"%d %d",&w[i],&s[i]);
    for(int i=0;iint X=*max_element(x,x+n);
    int Y=*max_element(y,y+m);
    for(int i=0;iif(w[i] > X && s[i] > Y)
    	{
    		puts("-1");
    		return 0;
    	}
    }
    if(m==0)
    {
    	sol();
    	return 0;
    }
    int lb=0,ub=t;
    vectorvec;
    for(int i=0;i{w[i],s[i]} );
    sort(vec.begin(),vec.end());
    sort(x,x+n);
    sort(y,y+m);
    for(int i=0;i{
    	pre[i] = lower_bound(x,x+n,vec[i].g)-x;
    }
    while(ub-lb > 1)
    {
        int mid=(lb+ub)>>1;
        int rem[n];
        fill(rem,rem+n,mid);
        int many=0;
        set<int>cur;
        for(int i=0;ibool ok=true;
        for(int i=0;i{
            if(cur.empty())
            {
                if(vec[i].sz > y[m-1-(many/mid)]){ ok=false; goto fail;}
                if(++many == 1LL*m*mid+1){ ok=false; goto fail;}
                continue;
            }
            set<int>::iterator id=cur.lower_bound(pre[i]);
            if(id == cur.end())
            {
                if(vec[i].sz > y[m-1-(many/mid)]){ ok=false; goto fail;}
                if(++many == 1LL*m*mid+1){ ok=false; goto fail;}
                continue;
            }
            rem[*id]--;
            if(!rem[*id])
            {
                cur.erase(id);
            }
        }
    fail:;
        if(ok) ub=mid;
        else lb=mid;
    }
    printf("%d\n",ub);
}