oj.uz

Submission #914659

# Submission time Handle Problem Language Result Execution time Memory
914659 2024-01-22T13:30:43 Z davitmarg Towers (NOI22_towers) C++17
18 / 100
 827 ms 125116 KB 
/*
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] && x[y[l][L].X].back() != y[l][L])
			L++;

        while(R >= 0 && used_x_down[y[l][R].X] && x[y[l][R].X].back() != y[l][R])
            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] && x[y[r][L].X][0] != y[r][L])
            L++;

        while (R >= 0 && used_x_up[y[r][R].X] && x[y[r][R].X][0] != y[r][R])
            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

16
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4


*/

Compilation message

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] && x[y[l][L].X].back() != y[l][L])
      |               ~~^~~~~~~~~~~~~
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] && x[y[r][L].X][0] != y[r][L])
      |               ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 51548 KB Output is correct
2 Correct 18 ms 51548 KB Output is correct
3 Correct 22 ms 51548 KB Output is correct
4 Correct 21 ms 51548 KB Output is correct
5 Correct 21 ms 51548 KB Output is correct
6 Correct 20 ms 51544 KB Output is correct
7 Correct 20 ms 51548 KB Output is correct
8 Correct 22 ms 51548 KB Output is correct
9 Correct 20 ms 51548 KB Output is correct
10 Correct 21 ms 51544 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 51548 KB Output is correct
2 Correct 18 ms 51548 KB Output is correct
3 Correct 22 ms 51548 KB Output is correct
4 Correct 21 ms 51548 KB Output is correct
5 Correct 21 ms 51548 KB Output is correct
6 Correct 20 ms 51544 KB Output is correct
7 Correct 20 ms 51548 KB Output is correct
8 Correct 22 ms 51548 KB Output is correct
9 Correct 20 ms 51548 KB Output is correct
10 Correct 21 ms 51544 KB Output is correct
11 Correct 21 ms 51800 KB Output is correct
12 Correct 20 ms 51548 KB Output is correct
13 Incorrect 22 ms 51804 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 57436 KB Output is correct
2 Correct 35 ms 58340 KB Output is correct
3 Correct 73 ms 67408 KB Output is correct
4 Correct 130 ms 85608 KB Output is correct
5 Correct 37 ms 58704 KB Output is correct
6 Correct 20 ms 53024 KB Output is correct
7 Correct 128 ms 83028 KB Output is correct
8 Correct 92 ms 77240 KB Output is correct
9 Correct 191 ms 97612 KB Output is correct
10 Correct 158 ms 89588 KB Output is correct
11 Correct 182 ms 94192 KB Output is correct
12 Correct 198 ms 93976 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 117296 KB Output is correct
2 Correct 447 ms 114064 KB Output is correct
3 Correct 422 ms 117312 KB Output is correct
4 Correct 444 ms 117116 KB Output is correct
5 Correct 457 ms 116960 KB Output is correct
6 Correct 827 ms 125116 KB Output is correct
7 Correct 802 ms 124772 KB Output is correct
8 Correct 787 ms 124816 KB Output is correct
9 Correct 803 ms 124852 KB Output is correct
10 Correct 777 ms 124788 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 51548 KB Output is correct
2 Correct 18 ms 51548 KB Output is correct
3 Correct 22 ms 51548 KB Output is correct
4 Correct 21 ms 51548 KB Output is correct
5 Correct 21 ms 51548 KB Output is correct
6 Correct 20 ms 51544 KB Output is correct
7 Correct 20 ms 51548 KB Output is correct
8 Correct 22 ms 51548 KB Output is correct
9 Correct 20 ms 51548 KB Output is correct
10 Correct 21 ms 51544 KB Output is correct
11 Correct 21 ms 51800 KB Output is correct
12 Correct 20 ms 51548 KB Output is correct
13 Incorrect 22 ms 51804 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 51548 KB Output is correct
2 Correct 18 ms 51548 KB Output is correct
3 Correct 22 ms 51548 KB Output is correct
4 Correct 21 ms 51548 KB Output is correct
5 Correct 21 ms 51548 KB Output is correct
6 Correct 20 ms 51544 KB Output is correct
7 Correct 20 ms 51548 KB Output is correct
8 Correct 22 ms 51548 KB Output is correct
9 Correct 20 ms 51548 KB Output is correct
10 Correct 21 ms 51544 KB Output is correct
11 Correct 21 ms 51800 KB Output is correct
12 Correct 20 ms 51548 KB Output is correct
13 Incorrect 22 ms 51804 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 51548 KB Output is correct
2 Correct 18 ms 51548 KB Output is correct
3 Correct 22 ms 51548 KB Output is correct
4 Correct 21 ms 51548 KB Output is correct
5 Correct 21 ms 51548 KB Output is correct
6 Correct 20 ms 51544 KB Output is correct
7 Correct 20 ms 51548 KB Output is correct
8 Correct 22 ms 51548 KB Output is correct
9 Correct 20 ms 51548 KB Output is correct
10 Correct 21 ms 51544 KB Output is correct
11 Correct 21 ms 51800 KB Output is correct
12 Correct 20 ms 51548 KB Output is correct
13 Incorrect 22 ms 51804 KB Output isn't correct
14 Halted 0 ms 0 KB -