oj.uz

Submission #758373

# Submission time Handle Problem Language Result Execution time Memory
758373 2023-06-14T14:14:23 Z jer033 Towers (NOI22_towers) C++17
18 / 100
 711 ms 29736 KB 
#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[0]=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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 75 ms 296 KB Output is correct
12 Correct 85 ms 304 KB Output is correct
13 Correct 73 ms 212 KB Output is correct
14 Correct 79 ms 296 KB Output is correct
15 Correct 79 ms 304 KB Output is correct
16 Correct 81 ms 304 KB Output is correct
17 Incorrect 88 ms 212 KB Extra information in the output file
18 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2680 KB Output is correct
2 Correct 41 ms 3068 KB Output is correct
3 Correct 129 ms 8976 KB Output is correct
4 Correct 263 ms 17308 KB Output is correct
5 Correct 43 ms 3340 KB Output is correct
6 Correct 9 ms 852 KB Output is correct
7 Correct 245 ms 16236 KB Output is correct
8 Correct 173 ms 10956 KB Output is correct
9 Correct 406 ms 23992 KB Output is correct
10 Correct 302 ms 20340 KB Output is correct
11 Correct 361 ms 25796 KB Output is correct
12 Correct 380 ms 25736 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 29624 KB Output is correct
2 Correct 625 ms 29544 KB Output is correct
3 Correct 599 ms 29624 KB Output is correct
4 Correct 617 ms 29652 KB Output is correct
5 Correct 612 ms 29736 KB Output is correct
6 Correct 627 ms 29612 KB Output is correct
7 Correct 631 ms 29644 KB Output is correct
8 Correct 711 ms 29564 KB Output is correct
9 Correct 673 ms 29728 KB Output is correct
10 Correct 661 ms 29716 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 75 ms 296 KB Output is correct
12 Correct 85 ms 304 KB Output is correct
13 Correct 73 ms 212 KB Output is correct
14 Correct 79 ms 296 KB Output is correct
15 Correct 79 ms 304 KB Output is correct
16 Correct 81 ms 304 KB Output is correct
17 Incorrect 88 ms 212 KB Extra information in the output file
18 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 75 ms 296 KB Output is correct
12 Correct 85 ms 304 KB Output is correct
13 Correct 73 ms 212 KB Output is correct
14 Correct 79 ms 296 KB Output is correct
15 Correct 79 ms 304 KB Output is correct
16 Correct 81 ms 304 KB Output is correct
17 Incorrect 88 ms 212 KB Extra information in the output file
18 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 75 ms 296 KB Output is correct
12 Correct 85 ms 304 KB Output is correct
13 Correct 73 ms 212 KB Output is correct
14 Correct 79 ms 296 KB Output is correct
15 Correct 79 ms 304 KB Output is correct
16 Correct 81 ms 304 KB Output is correct
17 Incorrect 88 ms 212 KB Extra information in the output file
18 Halted 0 ms 0 KB -