oj.uz

Submission #914897

# Submission time Handle Problem Language Result Execution time Memory
914897 2024-01-22T20:24:08 Z davitmarg Towers (NOI22_towers) C++17
18 / 100
 901 ms 126988 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 ax)
{
    int pos;
    if (used_x[ax] == 3)
    {
        used_x[ax]--;
        int last_y = last_x[ax].back();

        if (ly[last_y] == ry[last_y])
        {
            last_x[y[last_y][ly[last_y]].X].pop_back();
            ly[last_y]++;
        }
        else if (y[last_y][ly[last_y]].X == ax)
        {
            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(y[last_y][pos].X);
                last_x[y[last_y][pos].X].push_back(last_y);
			}
        }
        else if(y[last_y][ry[last_y]].X == ax)
        {
            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(y[last_y][pos].X);
                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(y[i][0].X);
       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(y[i].back().X);
           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 25 ms 61788 KB Output is correct
2 Correct 18 ms 57828 KB Output is correct
3 Correct 25 ms 61788 KB Output is correct
4 Correct 24 ms 61788 KB Output is correct
5 Correct 24 ms 59740 KB Output is correct
6 Correct 26 ms 60176 KB Output is correct
7 Correct 24 ms 59732 KB Output is correct
8 Correct 25 ms 57688 KB Output is correct
9 Correct 23 ms 57688 KB Output is correct
10 Correct 27 ms 60084 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 61788 KB Output is correct
2 Correct 18 ms 57828 KB Output is correct
3 Correct 25 ms 61788 KB Output is correct
4 Correct 24 ms 61788 KB Output is correct
5 Correct 24 ms 59740 KB Output is correct
6 Correct 26 ms 60176 KB Output is correct
7 Correct 24 ms 59732 KB Output is correct
8 Correct 25 ms 57688 KB Output is correct
9 Correct 23 ms 57688 KB Output is correct
10 Correct 27 ms 60084 KB Output is correct
11 Correct 25 ms 61788 KB Output is correct
12 Correct 24 ms 61788 KB Output is correct
13 Correct 25 ms 61788 KB Output is correct
14 Correct 26 ms 62000 KB Output is correct
15 Correct 26 ms 61788 KB Output is correct
16 Incorrect 23 ms 61788 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 59812 KB Output is correct
2 Correct 34 ms 60756 KB Output is correct
3 Correct 69 ms 66784 KB Output is correct
4 Correct 128 ms 77400 KB Output is correct
5 Correct 40 ms 60596 KB Output is correct
6 Correct 20 ms 56320 KB Output is correct
7 Correct 123 ms 77652 KB Output is correct
8 Correct 85 ms 70780 KB Output is correct
9 Correct 194 ms 88920 KB Output is correct
10 Correct 156 ms 81748 KB Output is correct
11 Correct 175 ms 85584 KB Output is correct
12 Correct 189 ms 85744 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 99560 KB Output is correct
2 Correct 319 ms 96648 KB Output is correct
3 Correct 333 ms 99628 KB Output is correct
4 Correct 310 ms 99916 KB Output is correct
5 Correct 344 ms 99668 KB Output is correct
6 Correct 864 ms 126808 KB Output is correct
7 Correct 901 ms 126864 KB Output is correct
8 Correct 854 ms 126988 KB Output is correct
9 Correct 880 ms 126720 KB Output is correct
10 Correct 886 ms 126804 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 61788 KB Output is correct
2 Correct 18 ms 57828 KB Output is correct
3 Correct 25 ms 61788 KB Output is correct
4 Correct 24 ms 61788 KB Output is correct
5 Correct 24 ms 59740 KB Output is correct
6 Correct 26 ms 60176 KB Output is correct
7 Correct 24 ms 59732 KB Output is correct
8 Correct 25 ms 57688 KB Output is correct
9 Correct 23 ms 57688 KB Output is correct
10 Correct 27 ms 60084 KB Output is correct
11 Correct 25 ms 61788 KB Output is correct
12 Correct 24 ms 61788 KB Output is correct
13 Correct 25 ms 61788 KB Output is correct
14 Correct 26 ms 62000 KB Output is correct
15 Correct 26 ms 61788 KB Output is correct
16 Incorrect 23 ms 61788 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 61788 KB Output is correct
2 Correct 18 ms 57828 KB Output is correct
3 Correct 25 ms 61788 KB Output is correct
4 Correct 24 ms 61788 KB Output is correct
5 Correct 24 ms 59740 KB Output is correct
6 Correct 26 ms 60176 KB Output is correct
7 Correct 24 ms 59732 KB Output is correct
8 Correct 25 ms 57688 KB Output is correct
9 Correct 23 ms 57688 KB Output is correct
10 Correct 27 ms 60084 KB Output is correct
11 Correct 25 ms 61788 KB Output is correct
12 Correct 24 ms 61788 KB Output is correct
13 Correct 25 ms 61788 KB Output is correct
14 Correct 26 ms 62000 KB Output is correct
15 Correct 26 ms 61788 KB Output is correct
16 Incorrect 23 ms 61788 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 61788 KB Output is correct
2 Correct 18 ms 57828 KB Output is correct
3 Correct 25 ms 61788 KB Output is correct
4 Correct 24 ms 61788 KB Output is correct
5 Correct 24 ms 59740 KB Output is correct
6 Correct 26 ms 60176 KB Output is correct
7 Correct 24 ms 59732 KB Output is correct
8 Correct 25 ms 57688 KB Output is correct
9 Correct 23 ms 57688 KB Output is correct
10 Correct 27 ms 60084 KB Output is correct
11 Correct 25 ms 61788 KB Output is correct
12 Correct 24 ms 61788 KB Output is correct
13 Correct 25 ms 61788 KB Output is correct
14 Correct 26 ms 62000 KB Output is correct
15 Correct 26 ms 61788 KB Output is correct
16 Incorrect 23 ms 61788 KB Output isn't correct
17 Halted 0 ms 0 KB -