Submission #914637

#	Time	Username	Problem	Language	Result	Execution time	Memory
914637		davitmarg	Towers (NOI22_towers)	C++17	5 / 100	376 ms	111188 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, k;
int ans[N];
pt p[N];
vector<pt> x[N], y[N];
int used_x_down[N], used_x_up[N];

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

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

    int r = k;

    for (int l = 1; l <= r; l++)
    {
        int L, R;
        if(y[l].empty())
            continue;

        while (r > l && y[r].empty())
            r--;

        if (l == r)
        {
            L = 0;
            R = y[l].size() - 1;
            while (L < y[l].size() && used_x_down[y[l][L].X] && used_x_up[y[l][L].X])
                L++;

            while (R >= 0 && used_x_down[y[l][R].X] && used_x_up[y[l][R].X])
                R--;

            if (L <= R)
            {
                ans[y[l][L].I] = 1;
                ans[y[l][R].I] = 1;
            }
            break;
        }

        L = 0;
        R = y[l].size() - 1;
        while(L < y[l].size() && used_x_down[y[l][L].X])
			L++;

        while(R >= 0 && used_x_down[y[l][R].X])
            R--;

        if (L <= R)
        {
            used_x_down[y[l][L].X] = 1;
            ans[y[l][L].I] = 1;
            used_x_down[y[l][R].X] = 1;
            ans[y[l][R].I] = 1;
		}

        L = 0;
        R = y[r].size() - 1;

        while(L < y[r].size() && used_x_up[y[r][L].X])
            L++;

        while (R >= 0 && used_x_up[y[r][R].X])
            R++;

        if (L <= R)
        {
            used_x_up[y[r][L].X] = 1;
			ans[y[r][L].I] = 1;
			used_x_up[y[r][R].X] = 1;
			ans[y[r][R].I] = 1;
        }
        
        r--;
    }

    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


9
1 1
2 1
3 1
1 2
2 2
3 2
1 3
2 3
3 3


7
1 1
3 1
1 2
2 2
3 2
1 3
3 3

3
1 1
1 2
1 3


*/

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             while (L < y[l].size() && used_x_down[y[l][L].X] && used_x_up[y[l][L].X])
      |                    ~~^~~~~~~~~~~~~
Main.cpp:95:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         while(L < y[l].size() && used_x_down[y[l][L].X])
      |               ~~^~~~~~~~~~~~~
Main.cpp:112:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         while(L < y[r].size() && used_x_up[y[r][L].X])
      |               ~~^~~~~~~~~~~~~

• Subtask 1: 5 / 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