Submission #990348

#	Time	Username	Problem	Language	Result	Execution time	Memory
990348		Pyqe	Longest Trip (IOI23_longesttrip)	C++17	100 / 100	12 ms	2752 KiB

longesttrip

#include <bits/stdc++.h>
#include "longesttrip.h"

using namespace std;

long long n,nn[2],nn2[2],ex[2][100069],ex2[2][100069],sq[100069],zs;

inline bool qr(vector<long long> v,vector<long long> v2)
{
	long long i,sz;
	vector<int> cv,cv2;
	
	sz=v.size();
	for(i=0;i<sz;i++)
	{
		cv.push_back(v[i]-1);
	}
	sz=v2.size();
	for(i=0;i<sz;i++)
	{
		cv2.push_back(v2[i]-1);
	}
	return are_connected(cv,cv2);
}

vector<int> longest_trip(int on,int d)
{
	long long i,j,ii,jj,k,l,e,lh,rh,md,zz;
	vector<long long> cv,cv2;
	vector<int> ret;
	
	n=on;
	for(ii=0;ii<2;ii++)
	{
		nn[ii]=0;
	}
	for(i=1;i<=n;i+=4)
	{
		for(ii=0;ii<2;ii++)
		{
			nn2[ii]=0;
		}
		for(j=i;j<=min(i+3,n);j++)
		{
			e=(!nn2[0]||nn2[1]<nn2[0])&&!!nn2[1];
			if(!nn2[e])
			{
				nn2[e]++;
				ex2[e][nn2[e]]=j;
			}
			else
			{
				k=ex2[e][nn2[e]];
				if(qr({j},{k}))
				{
					nn2[e]++;
					ex2[e][nn2[e]]=j;
					reverse(ex2[e]+1,ex2[e]+nn2[e]+1);
				}
				else
				{
					nn2[!e]++;
					ex2[!e][nn2[!e]]=j;
				}
			}
		}
		e=!nn[0]&&!!nn[1];
		if(!nn[e])
		{
			for(ii=0;ii<2;ii++)
			{
				for(j=1;j<=nn2[ii];j++)
				{
					nn[ii]++;
					ex[ii][nn[ii]]=ex2[ii][j];
				}
			}
		}
		else
		{
			k=ex[e][nn[e]];
			l=ex2[0][1];
			if(!nn[!e])
			{
				if(qr({k},{l}))
				{
					for(ii=0;ii<2;ii++)
					{
						for(j=1;j<=nn2[ii];j++)
						{
							nn[e^ii]++;
							ex[e^ii][nn[e^ii]]=ex2[ii][j];
						}
					}
				}
				else
				{
					for(j=nn2[0];j;j--)
					{
						nn[!e]++;
						ex[!e][nn[!e]]=ex2[0][j];
					}
					if(nn2[1])
					{
						k=ex[0][nn[0]];
						l=ex2[1][1];
						e=!qr({k},{l});
						for(j=1;j<=nn2[1];j++)
						{
							nn[e]++;
							ex[e][nn[e]]=ex2[1][j];
						}
						k=ex[0][nn[0]];
						l=ex[1][nn[1]];
						if(qr({k},{l}))
						{
							for(j=nn[1];j;j--)
							{
								nn[0]++;
								ex[0][nn[0]]=ex[1][j];
							}
							nn[1]=0;
						}
					}
				}
			}
			else
			{
				e^=!qr({k},{l});
				for(j=1;j<=nn2[0];j++)
				{
					nn[e]++;
					ex[e][nn[e]]=ex2[0][j];
				}
				if(!nn2[1])
				{
					k=ex[0][nn[0]];
					l=ex[1][nn[1]];
					if(qr({k},{l}))
					{
						for(j=nn[1];j;j--)
						{
							nn[0]++;
							ex[0][nn[0]]=ex[1][j];
						}
						nn[1]=0;
					}
				}
				else
				{
					k=ex[!e][nn[!e]];
					l=ex2[1][nn2[1]];
					if(qr({k},{l}))
					{
						for(j=nn2[1];j;j--)
						{
							nn[!e]++;
							ex[!e][nn[!e]]=ex2[1][j];
						}
						k=ex[0][nn[0]];
						l=ex[1][nn[1]];
						if(qr({k},{l}))
						{
							for(j=nn[1];j;j--)
							{
								nn[0]++;
								ex[0][nn[0]]=ex[1][j];
							}
							nn[1]=0;
						}
					}
					else
					{
						for(j=nn[!e];j;j--)
						{
							nn[e]++;
							ex[e][nn[e]]=ex[!e][j];
						}
						nn[!e]=0;
						k=ex[e][nn[e]];
						l=ex2[1][1];
						if(qr({k},{l}))
						{
							for(j=1;j<=nn2[1];j++)
							{
								nn[e]++;
								ex[e][nn[e]]=ex2[1][j];
							}
						}
						else
						{
							for(j=nn2[1];j;j--)
							{
								nn[!e]++;
								ex[!e][nn[!e]]=ex2[1][j];
							}
						}
					}
				}
			}
		}
	}
	zs=0;
	for(i=1;i<=nn[0];i++)
	{
		cv.push_back(ex[0][i]);
	}
	for(i=1;i<=nn[1];i++)
	{
		cv2.push_back(ex[1][i]);
	}
	if(!nn[0]||!nn[1]||!qr(cv,cv2))
	{
		e=nn[1]>nn[0];
		for(i=1;i<=nn[e];i++)
		{
			zs++;
			sq[zs]=ex[e][i];
		}
	}
	else
	{
		for(ii=0;ii<2;ii++)
		{
			k=ex[ii][1];
			l=ex[ii][nn[ii]];
			if(nn[ii]>2&&!qr({k},{l}))
			{
				break;
			}
		}
		if(ii<2)
		{
			for(ii=0;ii<2;ii++)
			{
				k=ex[0][1];
				for(jj=0;jj<2;jj++)
				{
					l=ex[1][1];
					if(!zs&&qr({k},{l}))
					{
						for(i=nn[0];i;i--)
						{
							zs++;
							sq[zs]=ex[0][i];
						}
						for(i=1;i<=nn[1];i++)
						{
							zs++;
							sq[zs]=ex[1][i];
						}
					}
					reverse(ex[1]+1,ex[1]+nn[1]+1);
				}
				reverse(ex[0]+1,ex[0]+nn[0]+1);
			}
		}
		else
		{
			cv2.clear();
			for(i=1;i<=nn[1];i++)
			{
				cv2.push_back(ex[1][i]);
			}
			for(ii=0;ii<2;ii++)
			{
				for(lh=1,rh=nn[ii];lh<=rh;)
				{
					md=(lh+rh)/2;
					cv.clear();
					for(i=1;i<=md;i++)
					{
						cv.push_back(ex[ii][i]);
					}
					if(qr(cv,cv2))
					{
						zz=md;
						rh=md-1;
					}
					else
					{
						lh=md+1;
					}
				}
				k=zz;
				swap(k,l);
				cv2.clear();
				for(i=1;i<=zz;i++)
				{
					cv2.push_back(ex[ii][i]);
				}
			}
			for(i=k+1;i<=nn[0];i++)
			{
				zs++;
				sq[zs]=ex[0][i];
			}
			for(i=1;i<=k;i++)
			{
				zs++;
				sq[zs]=ex[0][i];
			}
			for(i=l;i<=nn[1];i++)
			{
				zs++;
				sq[zs]=ex[1][i];
			}
			for(i=1;i<l;i++)
			{
				zs++;
				sq[zs]=ex[1][i];
			}
		}
	}
	for(i=1;i<=zs;i++)
	{
		ret.push_back(sq[i]-1);
	}
	return ret;
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:288:14: warning: 'zz' may be used uninitialized in this function [-Wmaybe-uninitialized]
  288 |     for(i=1;i<=zz;i++)
      |             ~^~~~

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