Submission #757986

#	Time	Username	Problem	Language	Result	Execution time	Memory
757986		jer033	Towers (NOI22_towers)	C++17	18 / 100	708 ms	29860 KiB

Main

#include <algorithm>
#include <iostream>

long long trios[1000005];
long long xis[1000005];
long long yis[1000005];
int subt4[1000005];
char answer[1000005];

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
	{
		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: 0 / 11
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 0 / 31
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19