oj.uz

Submission #914878

# Submission time Handle Problem Language Result Execution time Memory
914878 2024-01-22T19:55:42 Z davitmarg Towers (NOI22_towers) C++17
18 / 100
 1173 ms 180608 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[N];
vector<int> last_x[N];
int ly[N], ry[N];

void lesgo(int i, pt a)
{
    int pos;
    if (used_x[a.X] > 2)
    {
        used_x[a.X]--;
        int last_y = last_x[a.X].back();
        if (y[last_y][ly[last_y]].X == y[last_y][ry[last_y]].X)
        {
            last_x[y[last_y][ly[last_y]].X].pop_back();
            ly[last_y]++;
        }
        else if (y[last_y][ly[last_y]].X == a.X)
        {
            pos = ly[last_y];
            last_x[y[last_y][pos].X].pop_back();
            pos++;
			ly[last_y] = pos;
            if (pos < ry[last_y])
            {
				used_x[y[last_y][pos].X]++;
				lesgo(last_y, y[last_y][pos]);
                last_x[y[last_y][pos].X].push_back(last_y);
			}
        }
        else
        {
            pos = ry[last_y];
            last_x[y[last_y][pos].X].pop_back();
            pos--;
            ry[last_y] = pos;
            if (pos > ly[last_y])
            {
                used_x[y[last_y][pos].X]++;
				lesgo(last_y, y[last_y][pos]);
                last_x[y[last_y][pos].X].push_back(last_y);
            }
        }
    }
}

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

    for (int i = 1; i <= k; i++)
    {
       if(y[i].empty())
           continue;

       used_x[y[i][0].X]++;
       ly[i] = 0;
       lesgo(i, y[i][0]);
       last_x[y[i][0].X].push_back(i);


       ry[i] = y[i].size() - 1;
       if(y[i].size() != 1)
           used_x[y[i].back().X]++;

       lesgo(i, y[i].back());
       if (y[i].size() != 1)
          last_x[y[i].back().X].push_back(i);
    }


    for (int i = 1; i <= k; i++)
    {
        if(y[i].empty())
            continue;
        if(ly[i] <= ry[i])
            ans[y[i][ly[i]].I] = ans[y[i][ry[i]].I] = 1;
    }

    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


20
1 1
2 1
3 1
4 1
1 2
2 2
3 2
4 2
1 3
2 3
3 3
4 3
1 4
2 4
3 4
4 4
1 5
2 5
3 5
4 5

 
3
1 1
1 6
1 5


*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 84564 KB Output is correct
2 Correct 25 ms 80476 KB Output is correct
3 Correct 34 ms 84320 KB Output is correct
4 Correct 32 ms 84572 KB Output is correct
5 Correct 32 ms 82512 KB Output is correct
6 Correct 33 ms 82524 KB Output is correct
7 Correct 31 ms 82520 KB Output is correct
8 Correct 34 ms 80216 KB Output is correct
9 Correct 29 ms 80472 KB Output is correct
10 Correct 33 ms 82512 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 84564 KB Output is correct
2 Correct 25 ms 80476 KB Output is correct
3 Correct 34 ms 84320 KB Output is correct
4 Correct 32 ms 84572 KB Output is correct
5 Correct 32 ms 82512 KB Output is correct
6 Correct 33 ms 82524 KB Output is correct
7 Correct 31 ms 82520 KB Output is correct
8 Correct 34 ms 80216 KB Output is correct
9 Correct 29 ms 80472 KB Output is correct
10 Correct 33 ms 82512 KB Output is correct
11 Correct 33 ms 84484 KB Output is correct
12 Correct 32 ms 84536 KB Output is correct
13 Correct 34 ms 84424 KB Output is correct
14 Correct 35 ms 84568 KB Output is correct
15 Correct 34 ms 84572 KB Output is correct
16 Incorrect 30 ms 84568 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 84048 KB Output is correct
2 Correct 44 ms 85332 KB Output is correct
3 Correct 79 ms 96848 KB Output is correct
4 Correct 142 ms 114344 KB Output is correct
5 Correct 44 ms 85588 KB Output is correct
6 Correct 28 ms 81648 KB Output is correct
7 Correct 141 ms 111676 KB Output is correct
8 Correct 107 ms 105044 KB Output is correct
9 Correct 208 ms 127868 KB Output is correct
10 Correct 174 ms 119120 KB Output is correct
11 Correct 207 ms 124752 KB Output is correct
12 Correct 207 ms 124812 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 152912 KB Output is correct
2 Correct 448 ms 146376 KB Output is correct
3 Correct 440 ms 152916 KB Output is correct
4 Correct 482 ms 152772 KB Output is correct
5 Correct 479 ms 153036 KB Output is correct
6 Correct 1173 ms 180564 KB Output is correct
7 Correct 1127 ms 180304 KB Output is correct
8 Correct 1112 ms 180608 KB Output is correct
9 Correct 1128 ms 180440 KB Output is correct
10 Correct 1108 ms 180432 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 84564 KB Output is correct
2 Correct 25 ms 80476 KB Output is correct
3 Correct 34 ms 84320 KB Output is correct
4 Correct 32 ms 84572 KB Output is correct
5 Correct 32 ms 82512 KB Output is correct
6 Correct 33 ms 82524 KB Output is correct
7 Correct 31 ms 82520 KB Output is correct
8 Correct 34 ms 80216 KB Output is correct
9 Correct 29 ms 80472 KB Output is correct
10 Correct 33 ms 82512 KB Output is correct
11 Correct 33 ms 84484 KB Output is correct
12 Correct 32 ms 84536 KB Output is correct
13 Correct 34 ms 84424 KB Output is correct
14 Correct 35 ms 84568 KB Output is correct
15 Correct 34 ms 84572 KB Output is correct
16 Incorrect 30 ms 84568 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 84564 KB Output is correct
2 Correct 25 ms 80476 KB Output is correct
3 Correct 34 ms 84320 KB Output is correct
4 Correct 32 ms 84572 KB Output is correct
5 Correct 32 ms 82512 KB Output is correct
6 Correct 33 ms 82524 KB Output is correct
7 Correct 31 ms 82520 KB Output is correct
8 Correct 34 ms 80216 KB Output is correct
9 Correct 29 ms 80472 KB Output is correct
10 Correct 33 ms 82512 KB Output is correct
11 Correct 33 ms 84484 KB Output is correct
12 Correct 32 ms 84536 KB Output is correct
13 Correct 34 ms 84424 KB Output is correct
14 Correct 35 ms 84568 KB Output is correct
15 Correct 34 ms 84572 KB Output is correct
16 Incorrect 30 ms 84568 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 84564 KB Output is correct
2 Correct 25 ms 80476 KB Output is correct
3 Correct 34 ms 84320 KB Output is correct
4 Correct 32 ms 84572 KB Output is correct
5 Correct 32 ms 82512 KB Output is correct
6 Correct 33 ms 82524 KB Output is correct
7 Correct 31 ms 82520 KB Output is correct
8 Correct 34 ms 80216 KB Output is correct
9 Correct 29 ms 80472 KB Output is correct
10 Correct 33 ms 82512 KB Output is correct
11 Correct 33 ms 84484 KB Output is correct
12 Correct 32 ms 84536 KB Output is correct
13 Correct 34 ms 84424 KB Output is correct
14 Correct 35 ms 84568 KB Output is correct
15 Correct 34 ms 84572 KB Output is correct
16 Incorrect 30 ms 84568 KB Output isn't correct
17 Halted 0 ms 0 KB -