Submission #145235

#	Time	Username	Problem	Language	Result	Execution time	Memory
145235		TadijaSebez	Coin Collecting (JOI19_ho_t4)	C++11	0 / 100	2 ms	376 KiB

joi2019_ho_t4

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=100050;
int cnt[N][3];
ll ans=0;
queue<int> c[2],g[2];
void Solve()
{
	if(c[0].empty() || g[0].empty()) ans+=g[0].size()+c[0].size();
	else ans+=g[1].size()+c[1].size();
	vector<int> A,B;
	for(int i=0;i<2;i++) while(c[i].size()) A.pb(c[i].front()),c[i].pop();
	for(int i=0;i<2;i++) while(g[i].size()) B.pb(g[i].front()),g[i].pop();
	sort(A.begin(),A.end());
	sort(B.begin(),B.end());
	for(int i=0;i<A.size();i++) ans+=abs(A[i]-B[i]);
}
int main()
{
	int n,x,y;
	scanf("%i",&n);
	for(int i=1;i<=2*n;i++)
	{
		scanf("%i %i",&x,&y);
		if(x<1) ans+=1-x,x=1;
		if(x>n) ans+=x-n,x=n;
		if(y<1) ans+=1-y,y=1;
		if(y>2) ans+=y-2,y=2;
		cnt[x][y-1]++;
		//printf("X:%i Y:%i",x,y);
	}
	int has[2]={0,0};
	multiset<int> all[2];
	for(int i=1;i<=n;i++)
	{
		for(int k=1;k<=cnt[i][0];k++) all[0].insert(i);
		for(int k=1;k<=cnt[i][1];k++) all[1].insert(i);
	}
	for(int i=1;i<=n;i++)
	{
		while(all[0].size() && *all[0].begin()==i) has[0]++,all[0].erase(all[0].begin());
		while(all[1].size() && *all[1].begin()==i) has[1]++,all[1].erase(all[1].begin());
		bool done[2]={0,0};
		if(has[0]) done[0]=1,has[0]--;
		if(has[1]) done[1]=1,has[1]--;
		if(!done[0] && !done[1])
		{
			if(all[0].size() && all[1].size())
			{
				int fir=*all[0].begin()-i;
				int sec=*all[1].begin()-i;
				if(fir<=sec)
				{
					done[0]=1;
					ans+=fir;
					all[0].erase(all[0].begin());
				}
				else
				{
					done[1]=1;
					ans+=sec;
					all[1].erase(all[1].begin());
				}
			}
		}
		if(!done[0])
		{
			if(has[1]) done[0]=1,ans++,has[1]--;
			else
			{
				int fir=1e9,sec=1e9;
				if(all[0].size()) fir=*all[0].begin()-i;
				if(all[1].size()) sec=*all[1].begin()-i+1;
				if(fir<=sec)
				{
					ans+=fir;
					done[0]=1;
					all[0].erase(all[0].begin());
				}
				else
				{
					ans+=sec;
					done[0]=1;
					all[1].erase(all[1].begin());
				}
			}
		}
		if(!done[1])
		{
			if(has[0]) done[1]=1,ans++,has[0]--;
			else
			{
				int fir=1e9,sec=1e9;
				if(all[1].size()) fir=*all[1].begin()-i;
				if(all[0].size()) sec=*all[0].begin()-i+1;
				if(fir<=sec)
				{
					ans+=fir;
					done[1]=1;
					all[1].erase(all[1].begin());
				}
				else
				{
					ans+=sec;
					done[1]=1;
					all[0].erase(all[0].begin());
				}
			}
		}
		ans+=has[0]+has[1];
		//printf("%lld\n",ans);
	}
	//printf("CNT:\n");
	/*for(int j=0;j<2;j++)
	{
		for(int i=1;i<=n;i++)
		{
			//printf("%i ",cnt[i][j]);
			for(int k=2;k<=cnt[i][j];k++) c[j].push(i);
			if(cnt[i][j]==0) g[j].push(i);
		}
		//printf("\n");
	}*/
	/*while(c[0].size() && c[1].size() && g[0].size() && g[1].size())
	{
		int c0=c[0].front();
		int c1=c[1].front();
		int q0=g[0].front();
		int q1=g[1].front();
		if(c0<=c1)
		{
			if(abs(c0-q0)+abs(c1-q1)<=abs(c0-q1)+abs(c1-q0)+2)
			{
				ans+=abs(c0-q0)+abs(c1-q1);
				c[0].pop();
				g[0].pop();
				c[1].pop();
				g[1].pop();
				//printf("%i 0 %i 0\n",c0,q0);
			}
			else
			{
				ans+=abs(c0-q1)+1;
				c[0].pop();
				g[1].pop();
				//printf("%i 0 %i 1\n",c0,q1);
			}
		}
		else
		{
			if(abs(c0-q0)+abs(c1-q1)<=abs(c0-q1)+abs(c1-q0)+2)
			{
				ans+=abs(c0-q0)+abs(c1-q1);
				c[0].pop();
				g[0].pop();
				c[1].pop();
				g[1].pop();
				//printf("%i 1 %i 1\n",c1,q1);
			}
			else
			{
				ans+=abs(c1-q0)+1;
				c[1].pop();
				g[0].pop();
				//printf("%i 1 %i 0\n",c1,q0);
			}
		}*/
		/*if(c0<c1)
		{
			if(q0<=q1)
			{
				ans+=abs(c0-q0);
				c[0].pop();
				q[0].pop();
			}
			else
			{
				if(q1<c0)
				{
					ans+=abs(c0-q1)+1;
					c[0].pop();
					q[1].pop();
				}
				else
				{
					if(c1<=q1)
					{
						ans+=abs(c0-q0)+abs(c1-q1);
						c[0].pop();
						c[1].pop();
						q[0].pop();
						q[1].pop();
					}
					else
					{

					}
				}
			}
		}
		else if(c1<c0)
		{

		}
		else
		{
			if(q0<=q1)
			{
				ans+=abs(c0-q0);
				c[0].pop();
				q[0].pop();
			}
			else
			{
				ans+=abs(c1-q1);
				c[1].pop();
				q[1].pop();
			}
		}*/
	//}
	//Solve();
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

joi2019_ho_t4.cpp: In function 'void Solve()':
joi2019_ho_t4.cpp:18:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<A.size();i++) ans+=abs(A[i]-B[i]);
              ~^~~~~~~~~
joi2019_ho_t4.cpp: In function 'int main()':
joi2019_ho_t4.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
joi2019_ho_t4.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63