Submission #758377

#	Time	Username	Problem	Language	Result	Execution time	Memory
758377		jer033	Towers (NOI22_towers)	C++17	29 / 100	664 ms	29720 KiB

Main

#include <algorithm>
#include <iostream>

long long trios[1000005];
long long xis[1000005];
long long yis[1000005];
int subt4[1000005];
char answer[1000005];
char potentialans[20];
char happy[20];
int ac[20];

using namespace std;
long long const mult = 1000007;//10^6 + 7

long long inde(long long a, long long b, long long x, long long y)
{
	b=0;
	return (x-1)*a+y+b-1;//yeah b isn't really needed after all
}

int main()
{
	int n;
	cin >> n;
	if (n==3)
	{
		int a, b, c, d, e, f;
		cin >> a >> d >> b >> e >> c >> f;
		if (a==b and b==c)
		{
			if (d>e and e>f)
			{
				cout << "101";
			}
			else if (d<e and e<f)
			{
				cout << "101";
			}
			else if (e>d and d>f)
			{
				cout << "011";
			}
			else if (e<d and d<f)
			{
				cout << "011";
			}
			else if (d>f and f>e)
			{
				cout << "110";
			}
			else if (d<f and f<e)
			{
				cout << "110";
			}
		}
		else if (d==e and e==f)
		{
			if (a>b and b>c)
			{
				cout << "101";
			}
			else if (a<b and b<c)
			{
				cout << "101";
			}
			else if (b>a and a>c)
			{
				cout << "011";
			}
			else if (b<a and a<c)
			{
				cout << "011";
			}
			else if (a>c and c>b)
			{
				cout << "110";
			}
			else if (a<c and c<b)
			{
				cout << "110";
			}
		}
		else
		{
			cout << "111";
		}
		cout << '\n';
	}
	else if (n<=2)
	{
		if (n==2)
		{
			cout << "1";
		}
		cout << "1\n";
	}
	else if (n<=16)
	{
		//consider each possibility: tower on tower off
		//check ff: at most 2 towers per column/row, all towers are good
		for (int i=0; i<n; i++)
		{
			cin >> xis[i] >> yis[i];
		}
		for (int i=0; i<(1<<n); i++)
		{
			int k=i;
			ac[n]=1;
			for (int j=0; j<n; j++)
			{
				if (k>=(1<<(n-1-j)))
				{
					k-=(1<<(n-1-j));
					potentialans[j]='1';
					ac[j]=1;
				}
				else
				{
					potentialans[j]='0';
					ac[j]=0;
				}
			}
			for (int j=0; j<n; j++)
			{
				for (int k=j+1; k<n; k++)
				{
					for (int l=k+1; l<n; l++)
					{
						if (xis[j]==xis[k] and xis[k]==xis[l])
						{
							if (potentialans[j]=='1' and potentialans[k]=='1' and potentialans[l]=='1')
								ac[n]=0;
							if (yis[j]>yis[k] and yis[j]<yis[l] and potentialans[k]=='1' and potentialans[l]=='1')
							{
								ac[j]=1;
							}
							if (yis[j]>yis[l] and yis[j]<yis[k] and potentialans[k]=='1' and potentialans[l]=='1')
							{
								ac[j]=1;
							}
							if (yis[k]>yis[j] and yis[k]<yis[l] and potentialans[j]=='1' and potentialans[l]=='1')
							{
								ac[k]=1;
							}
							if (yis[k]>yis[l] and yis[k]<yis[j] and potentialans[j]=='1' and potentialans[l]=='1')
							{
								ac[k]=1;
							}
							if (yis[l]>yis[j] and yis[l]<yis[k] and potentialans[k]=='1' and potentialans[j]=='1')
							{
								ac[l]=1;
							}
							if (yis[l]>yis[k] and yis[l]<yis[j] and potentialans[k]=='1' and potentialans[j]=='1')
							{
								ac[l]=1;
							}
						}
						else if (yis[j]==yis[k] and yis[k]==yis[l])
						{
							if (potentialans[j]=='1' and potentialans[k]=='1' and potentialans[l]=='1')
								ac[n]=0;
							if (xis[j]>xis[k] and xis[j]<xis[l] and potentialans[k]=='1' and potentialans[l]=='1')
							{
								ac[j]=1;
							}
							if (xis[j]>xis[l] and xis[j]<xis[k] and potentialans[k]=='1' and potentialans[l]=='1')
							{
								ac[j]=1;
							}
							if (xis[k]>xis[j] and xis[k]<xis[l] and potentialans[j]=='1' and potentialans[l]=='1')
							{
								ac[k]=1;
							}
							if (xis[k]>xis[l] and xis[k]<xis[j] and potentialans[j]=='1' and potentialans[l]=='1')
							{
								ac[k]=1;
							}
							if (xis[l]>xis[j] and xis[l]<xis[k] and potentialans[k]=='1' and potentialans[j]=='1')
							{
								ac[l]=1;
							}
							if (xis[l]>xis[k] and xis[l]<xis[j] and potentialans[k]=='1' and potentialans[j]=='1')
							{
								ac[l]=1;
							}
						}
					}
				}
			}
			int totall=0;
			for (int j=0; j<=n; j++)
			{
				totall=totall+ac[j];
			}
			if (totall==n+1)
			{
				cout << potentialans << '\n';
				for (int i=0; i<n; i++)
					happy[i]=potentialans[i];
			}
		}
		//cout << happy << '\n';
	}
	else
	{
		int four=1;
		long long b=0;
		long long a=0;
		for (int i=0; i<n; i++)
		{
			cin >> xis[i] >> yis[i];
			b=max(b, xis[i]);
			a=max(a, yis[i]);
			trios[i]=mult*mult*yis[i]+mult*xis[i]+i;
			subt4[xis[i]]++;
			if (subt4[xis[i]]>=3)
				four=0;
		}
		if (four)
		{
			for (int i=0; i<n; i++)
			{
				answer[i]='1';
			}
			sort(trios, trios+n);
			int sindex=0;
			int eindex=0;
			while (sindex<n)
			{
				while (trios[eindex]/(mult*mult) == trios[eindex+1]/(mult*mult))
				{
					eindex++;
				}
				for (int i=sindex+1; i<eindex; i++)
				{
					answer[trios[i]%mult] = '0';
				}
				sindex=eindex+1;
				eindex=sindex+1-1;
			}
			cout << answer << '\n';
		}
		else
		{
			//assume this is subtask 3, then we already have our values of b and a
			for (int i=0; i<n; i++)
			{
				answer[i]='0';
			}
			if (a==b)
			{
				for (int i=1; i<=a; i++)
				{
					answer[inde(a, b, i, i)]='1';
					answer[inde(a, b, i, a+1-i)]='1';
				}
			}
			else if (a>b)
			{
				for (long long i=1; i<=b; i++)
				{
					answer[inde(a, b, i, min(i, b+1-i))]='1';
					answer[inde(a, b, i, a+1-min(i, b+1-i))]='1';
				}
			}
			else
			{
				for (long long i=1; i<=a; i++)
				{
					answer[inde(a, b, min(i, a+1-i), i)]='1';
					answer[inde(a, b, b+1-min(i, a+1-i), i)]='1';
				}
			}
			cout << answer << '\n';
		}
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 0 / 31
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19