oj.uz

Submission #914879

# Submission time Handle Problem Language Result Execution time Memory
914879 2024-01-22T20:05:02 Z davitmarg Towers (NOI22_towers) C++17
18 / 100
 963 ms 120168 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> 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]);
    }

    for (int i = 1; i <= k; i++)
        sort(all(y[i]));

    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 (ly[i] != ry[i])
       {
           used_x[y[i].back().X]++;
           lesgo(i, y[i].back());
           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

9
1 1
1 2
2 2
1 3
1 4
1 5
2 5
1 6
1 7


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

 


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


*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 61788 KB Output is correct
2 Correct 18 ms 57692 KB Output is correct
3 Correct 25 ms 62020 KB Output is correct
4 Correct 24 ms 61788 KB Output is correct
5 Correct 25 ms 59740 KB Output is correct
6 Correct 26 ms 59736 KB Output is correct
7 Correct 24 ms 59916 KB Output is correct
8 Correct 27 ms 57860 KB Output is correct
9 Correct 21 ms 57900 KB Output is correct
10 Correct 25 ms 59736 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 61788 KB Output is correct
2 Correct 18 ms 57692 KB Output is correct
3 Correct 25 ms 62020 KB Output is correct
4 Correct 24 ms 61788 KB Output is correct
5 Correct 25 ms 59740 KB Output is correct
6 Correct 26 ms 59736 KB Output is correct
7 Correct 24 ms 59916 KB Output is correct
8 Correct 27 ms 57860 KB Output is correct
9 Correct 21 ms 57900 KB Output is correct
10 Correct 25 ms 59736 KB Output is correct
11 Correct 24 ms 61788 KB Output is correct
12 Correct 25 ms 61788 KB Output is correct
13 Correct 25 ms 61920 KB Output is correct
14 Correct 26 ms 61788 KB Output is correct
15 Correct 26 ms 62024 KB Output is correct
16 Incorrect 23 ms 61956 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 32 ms 59736 KB Output is correct
2 Correct 36 ms 59952 KB Output is correct
3 Correct 64 ms 65104 KB Output is correct
4 Correct 121 ms 75056 KB Output is correct
5 Correct 38 ms 59732 KB Output is correct
6 Correct 20 ms 56152 KB Output is correct
7 Correct 121 ms 74832 KB Output is correct
8 Correct 80 ms 68692 KB Output is correct
9 Correct 187 ms 84952 KB Output is correct
10 Correct 163 ms 78424 KB Output is correct
11 Correct 173 ms 81472 KB Output is correct
12 Correct 183 ms 81676 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 93428 KB Output is correct
2 Correct 301 ms 93268 KB Output is correct
3 Correct 323 ms 93460 KB Output is correct
4 Correct 313 ms 93200 KB Output is correct
5 Correct 311 ms 93268 KB Output is correct
6 Correct 903 ms 119812 KB Output is correct
7 Correct 921 ms 119876 KB Output is correct
8 Correct 963 ms 120012 KB Output is correct
9 Correct 915 ms 120148 KB Output is correct
10 Correct 918 ms 120168 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 61788 KB Output is correct
2 Correct 18 ms 57692 KB Output is correct
3 Correct 25 ms 62020 KB Output is correct
4 Correct 24 ms 61788 KB Output is correct
5 Correct 25 ms 59740 KB Output is correct
6 Correct 26 ms 59736 KB Output is correct
7 Correct 24 ms 59916 KB Output is correct
8 Correct 27 ms 57860 KB Output is correct
9 Correct 21 ms 57900 KB Output is correct
10 Correct 25 ms 59736 KB Output is correct
11 Correct 24 ms 61788 KB Output is correct
12 Correct 25 ms 61788 KB Output is correct
13 Correct 25 ms 61920 KB Output is correct
14 Correct 26 ms 61788 KB Output is correct
15 Correct 26 ms 62024 KB Output is correct
16 Incorrect 23 ms 61956 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 61788 KB Output is correct
2 Correct 18 ms 57692 KB Output is correct
3 Correct 25 ms 62020 KB Output is correct
4 Correct 24 ms 61788 KB Output is correct
5 Correct 25 ms 59740 KB Output is correct
6 Correct 26 ms 59736 KB Output is correct
7 Correct 24 ms 59916 KB Output is correct
8 Correct 27 ms 57860 KB Output is correct
9 Correct 21 ms 57900 KB Output is correct
10 Correct 25 ms 59736 KB Output is correct
11 Correct 24 ms 61788 KB Output is correct
12 Correct 25 ms 61788 KB Output is correct
13 Correct 25 ms 61920 KB Output is correct
14 Correct 26 ms 61788 KB Output is correct
15 Correct 26 ms 62024 KB Output is correct
16 Incorrect 23 ms 61956 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 61788 KB Output is correct
2 Correct 18 ms 57692 KB Output is correct
3 Correct 25 ms 62020 KB Output is correct
4 Correct 24 ms 61788 KB Output is correct
5 Correct 25 ms 59740 KB Output is correct
6 Correct 26 ms 59736 KB Output is correct
7 Correct 24 ms 59916 KB Output is correct
8 Correct 27 ms 57860 KB Output is correct
9 Correct 21 ms 57900 KB Output is correct
10 Correct 25 ms 59736 KB Output is correct
11 Correct 24 ms 61788 KB Output is correct
12 Correct 25 ms 61788 KB Output is correct
13 Correct 25 ms 61920 KB Output is correct
14 Correct 26 ms 61788 KB Output is correct
15 Correct 26 ms 62024 KB Output is correct
16 Incorrect 23 ms 61956 KB Output isn't correct
17 Halted 0 ms 0 KB -