Submission #124347

#	Time	Username	Problem	Language	Result	Execution time	Memory
124347		tinjyu	Aliens (IOI16_aliens)	C++14	4 / 100	2 ms	380 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
long long int n,m,k,x[100005],y[100005],t[100005][2];
int qs(int s,int e)
{
	if(s>=e)return 0;
	long long int mid=(s+e)/2,l=s,r=mid+1,p=s;
	qs(s,mid);
	qs(mid+1,e);
	while(l<=mid && r<=e)
	{
		if(x[l]<x[r] || (x[l]==x[r] && y[l]>y[r]))
		{
			t[p][0]=x[l];
			t[p][1]=y[l];
			l++;
			p++;
		}
		else
		{
			t[p][0]=x[r];
			t[p][1]=y[r];
			r++;
			p++;
		}
	}
	while(l<=mid)
	{
		t[p][0]=x[l];
		t[p][1]=y[l];
		l++;
		p++;
	}
	while(r<=e)
	{
		t[p][0]=x[r];
		t[p][1]=y[r];
		r++;
		p++;
	}
	for(int i=s;i<=e;i++)
	{
		x[i]=t[i][0];
		y[i]=t[i][1];
	}
}
long long take_photos(int u, int v, int z, std::vector<int> a, std::vector<int> b) {
	n=u;
	m=v;
	k=z;
	for(int i=0;i<n;i++)
	{
		x[i]=a[i];
		y[i]=b[i];
		if(x[i]>y[i])swap(x[i],y[i]);
	}
	qs(0,n-1);
	long long int cnt=-1,tmp=-1,ans=0;
	for(int i=0;i<n;i++)
	{
		if(y[i]>tmp)
		{
			cnt++;
			x[cnt]=x[i];
			y[cnt]=y[i];
			//cout<<x[i]<<" "<<y[i]<<endl;
			ans+=(y[i]-x[i]+1)*(y[i]-x[i]+1);
			if(x[i]-1<tmp)ans-=(tmp-x[i]+1)*(tmp-x[i]+1);
			//cout<<ans<<" "<<tmp<<endl;
			tmp=y[i];
		}
	}
	n=cnt+1;
	while(n>k)
	{
		tmp=999999999;
		//cout<<n<<" "<<k<<" "<<ans<<endl;
		for(int i=0;i<n-1;i++)
		{
			long long int tm=0;
			long long int tmpx=min(x[i],x[i+1]),tmpy=max(y[i],y[i+1]);
			if(x[i+1]-1<y[i])tm=abs(x[i]-x[i+1])*(y[i]-y[i+1])*2;
			else 
			{
				tm=(tmpy-tmpx+1)*(tmpy-tmpx+1)-(y[i]-x[i]+1)*(y[i]-x[i]+1)-(y[i+1]-x[i+1]+1)*(y[i+1]-x[i+1]+1);
				//cout<<(tmpy-tmpx+1)*(tmpy-tmpx+1)<<" "<<(y[i]-x[i]+1)*(y[i]-x[i]+1)<<" "<<(y[i+1]-x[i+1]+1)*(y[i+1]-x[i+1]+1)<<endl;
			}
			if(tm<tmp)
			{
				cnt=i;
				tmp=tm;
			}
		}
		ans+=tmp;;
		y[cnt]=y[cnt+1];
		for(int i=cnt+1;i<n-1;i++)
		{
			x[i]=x[i+1];
			y[i]=y[i+1];
		}
		n--;
	}
	return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'int qs(int, int)':
aliens.cpp:47:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 4 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40