Submission #914499

#	Time	Username	Problem	Language	Result	Execution time	Memory
914499		davitmarg	Towers (NOI22_towers)	C++17	0 / 100	471 ms	1048576 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 Y first.first
#define X first.second
#define I second
#define pt pair<pair<int,int>, int>

int n;
int ans[N];
int used_x[N], used_y[N];
pt p[N];
deque<pt> x[N], y[N];
set<pt> s;

void lesgo(pt a)
{
    ans[a.I] = 1;
    if (!y[a.Y].empty() && y[a.Y][0] == a && !used_y[a.Y])
    {
        pt b = y[a.Y].back();
        ans[b.I] = 1;
        while(!y[a.Y].empty())
        {
            s.erase(y[a.Y].back());
            y[a.Y].pop_back();
        }
        used_y[a.Y] = 1;
        if(b != a)
            lesgo(b);
    }
    else if (!y[a.Y].empty() && y[a.Y].back() == a && !used_y[a.Y])
    {
        pt b = y[a.Y][0];
        ans[b.I] = 1;
        while (!y[a.Y].empty())
        {
			s.erase(y[a.Y][0]);
			y[a.Y].pop_front();
		}
		used_y[a.Y] = 1;
        if (b != a)
            lesgo(b);
    }

    if (!x[a.X].empty() && x[a.X][0] == a && !used_x[a.X])
    {
        pt b = x[a.X].back();
		ans[b.I] = 1;
        while (!x[a.X].empty())
        {
			s.erase(x[a.X].back());
			x[a.X].pop_back();
        }
        used_x[a.X] = 1;
        if (b != a)
            lesgo(b);
    }
    else if (!x[a.X].empty() && x[a.X].back() == a && !used_x[a.X])
    {
        pt b = x[a.X][0];
        ans[b.I] = 1;
		while (!x[a.X].empty())
		{
            s.erase(x[a.X][0]);
            x[a.X].pop_front();
        }
        used_x[a.X] = 1;
        if (b != a)
            lesgo(b);
    }
}

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++)
    {
        s.insert(p[i]);
        x[p[i].X].push_back(p[i]);
        y[p[i].Y].push_back(p[i]);
    }


    for (int i = 1; i <= 1000 * 1000; 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; });
    }

    while (!s.empty())
    {
        pt a = *s.begin();
        lesgo(a);
    }

    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;
}

/*



*/

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