oj.uz

Submission #758362

# Submission time Handle Problem Language Result Execution time Memory
758362 2023-06-14T13:58:45 Z jer033 Towers (NOI22_towers) C++17
18 / 100
 707 ms 29672 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)
			{
				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 1 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 1 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 1 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 1 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 1 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 1 ms 212 KB Output is correct
11 Correct 88 ms 212 KB Output is correct
12 Correct 102 ms 332 KB Output is correct
13 Correct 78 ms 212 KB Output is correct
14 Correct 110 ms 300 KB Output is correct
15 Correct 93 ms 212 KB Output is correct
16 Correct 86 ms 312 KB Output is correct
17 Incorrect 116 ms 300 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2636 KB Output is correct
2 Correct 51 ms 3144 KB Output is correct
3 Correct 132 ms 8940 KB Output is correct
4 Correct 255 ms 17276 KB Output is correct
5 Correct 50 ms 3340 KB Output is correct
6 Correct 10 ms 860 KB Output is correct
7 Correct 277 ms 16208 KB Output is correct
8 Correct 159 ms 10888 KB Output is correct
9 Correct 390 ms 24012 KB Output is correct
10 Correct 337 ms 20460 KB Output is correct
11 Correct 389 ms 25744 KB Output is correct
12 Correct 398 ms 25668 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 597 ms 29660 KB Output is correct
2 Correct 645 ms 29644 KB Output is correct
3 Correct 622 ms 29544 KB Output is correct
4 Correct 615 ms 29672 KB Output is correct
5 Correct 626 ms 29548 KB Output is correct
6 Correct 632 ms 29572 KB Output is correct
7 Correct 707 ms 29564 KB Output is correct
8 Correct 680 ms 29548 KB Output is correct
9 Correct 677 ms 29664 KB Output is correct
10 Correct 657 ms 29604 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 1 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 1 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 1 ms 212 KB Output is correct
11 Correct 88 ms 212 KB Output is correct
12 Correct 102 ms 332 KB Output is correct
13 Correct 78 ms 212 KB Output is correct
14 Correct 110 ms 300 KB Output is correct
15 Correct 93 ms 212 KB Output is correct
16 Correct 86 ms 312 KB Output is correct
17 Incorrect 116 ms 300 KB Output isn't correct
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 1 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 1 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 1 ms 212 KB Output is correct
11 Correct 88 ms 212 KB Output is correct
12 Correct 102 ms 332 KB Output is correct
13 Correct 78 ms 212 KB Output is correct
14 Correct 110 ms 300 KB Output is correct
15 Correct 93 ms 212 KB Output is correct
16 Correct 86 ms 312 KB Output is correct
17 Incorrect 116 ms 300 KB Output isn't correct
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 1 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 1 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 1 ms 212 KB Output is correct
11 Correct 88 ms 212 KB Output is correct
12 Correct 102 ms 332 KB Output is correct
13 Correct 78 ms 212 KB Output is correct
14 Correct 110 ms 300 KB Output is correct
15 Correct 93 ms 212 KB Output is correct
16 Correct 86 ms 312 KB Output is correct
17 Incorrect 116 ms 300 KB Output isn't correct
18 Halted 0 ms 0 KB -