Submission #914608

#	Time	Username	Problem	Language	Result	Execution time	Memory
914608		davitmarg	Towers (NOI22_towers)	C++98	12 / 100	2065 ms	219424 KiB

Main

/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <random>
#include <chrono>
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair    
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;

const int N = 1000006;

#define X first.first
#define Y first.second
#define I second
#define pt pair<pair<int,int>, int>

int n;
int ans[N];
pt p[N];
map<int, set<pt>> x, y;
int used[N];

void lesgo(pt a)
{
    x[a.X].insert(a);
    y[a.Y].insert(a);
    ans[a.I] = 1;
    used[a.I] = 1;
    if (!y[a.Y].empty() && *y[a.Y].begin() == a)
    {
        pt last = a;
        bool f = 0;
        for (auto it = y[a.Y].begin(); it != y[a.Y].end(); ++it)
        {
            pt b = *it;
            if (b == a)
                continue;
            if (ans[b.I])
            {
                f = 1;
				break;
            }
            if(!x[b.X].empty() && !used[b.I] && (*x[b.X].begin() == b || *x[b.X].rbegin() == b))
				last = b;
            used[b.I] = 1;
            x[b.X].erase(b);
        }

        y[a.Y].clear();
        if (!f)
        {
            ans[last.I] = 1;
            if (last != a)
                lesgo(last);
        }
    }
    else if (!y[a.Y].empty() && *y[a.Y].rbegin() == a)
    {
        pt last = a;
        bool f = 0;
        for (auto it = y[a.Y].rbegin(); it != y[a.Y].rend(); ++it)
        {
            pt b = *it;
            if (b == a)
				continue;
               
            if (ans[b.I])
            {
				f = 1;
				break;
			}

			if (!x[b.X].empty() && !used[b.I] && (*x[b.X].begin() == b || *x[b.X].rbegin() == b))
                last = b;
            used[b.I] = 1;
            x[b.X].erase(b);
        }

        y[a.Y].clear();

        if (!f)
        {
            ans[last.I] = 1;
            if (last != a)
                lesgo(last);
        }
    }


    if (!x[a.X].empty() && *x[a.X].begin() == a)
    {
		pt last = a;
		bool f = 0;
        for (auto it = x[a.X].begin(); it != x[a.X].end(); ++it)
        {
			pt b = *it;
			if (b == a)
				continue;
            if (ans[b.I])
            {
				f = 1;
				break;
			}
			if (!y[b.Y].empty() && !used[b.I] && (*y[b.Y].begin() == b || *y[b.Y].rbegin() == b))
				last = b;
			used[b.I] = 1;
            y[b.Y].erase(b);
		}

		x[a.X].clear();
        if (!f)
        {
			ans[last.I] = 1;
			if (last != a)
				lesgo(last);
		}
	}
    else if (!x[a.X].empty() && *x[a.X].rbegin() == a)
    {
		pt last = a;
		bool f = 0;
        for (auto it = x[a.X].rbegin(); it != x[a.X].rend(); ++it)
        {
			pt b = *it;
			if (b == a)
				continue;
            if (ans[b.I])
            {
				f = 1;
				break;
			}
			if (!y[b.Y].empty() && !used[b.I] && (*y[b.Y].begin() == b || *y[b.Y].rbegin() == b))
				last = b;
			used[b.I] = 1;
            y[b.Y].erase(b);
		}

		x[a.X].clear();

        if (!f)
        {
			ans[last.I] = 1;
			if (last != a)
				lesgo(last);
		}
	}   
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i].X >> p[i].Y;
        p[i].I = i;
    }

    for (int i = 1; i <= n; i++)
    {
        x[p[i].X].insert(p[i]);
        y[p[i].Y].insert(p[i]);
    }

    for (int i = 0; i < N; i++)
    {
        // sort(all(x[i]), [](pt a, pt b) {return a.Y < b.Y; });
        // sort(all(y[i]), [](pt a, pt b) {return a.X < b.X; });
    }

    sort(p + 1, p + 1 + n, [](pt a, pt b) {
        if(a.Y == b.Y)
            return a.X < b.X;
        return a.Y < b.Y; 
    });

    for (int i = 1; i <= n; i++)
    {
        if(used[p[i].I])
            continue;
        lesgo(p[i]);
    }

    for (int i = 1; i <= n; i++)
        cout << ans[i];
    cout << endl;

}




int main()
{
    fastIO;
    int T = 1;
    //cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

/*

8
1 1
2 1
3 1
1 2
2 2
3 2
2 3
3 3


*/

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