# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
757981 | jer033 | Towers (NOI22_towers) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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+j+b;//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;
for (int i=0; i<n; i++)
{
long long b=0;
long long a=0;
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 (int 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 (int 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';
}
}
}