oj.uz

Submission #914883

# Submission time Handle Problem Language Result Execution time Memory
914883 2024-01-22T20:09:44 Z davitmarg Towers (NOI22_towers) C++17
18 / 100
 962 ms 120040 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++)
    {
        assert (used_x[i] <= 2);
        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 24 ms 61788 KB Output is correct
2 Correct 19 ms 57688 KB Output is correct
3 Correct 26 ms 61776 KB Output is correct
4 Correct 24 ms 61788 KB Output is correct
5 Correct 25 ms 59740 KB Output is correct
6 Correct 25 ms 59740 KB Output is correct
7 Correct 23 ms 59740 KB Output is correct
8 Correct 25 ms 57692 KB Output is correct
9 Correct 22 ms 57908 KB Output is correct
10 Correct 24 ms 59728 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 61788 KB Output is correct
2 Correct 19 ms 57688 KB Output is correct
3 Correct 26 ms 61776 KB Output is correct
4 Correct 24 ms 61788 KB Output is correct
5 Correct 25 ms 59740 KB Output is correct
6 Correct 25 ms 59740 KB Output is correct
7 Correct 23 ms 59740 KB Output is correct
8 Correct 25 ms 57692 KB Output is correct
9 Correct 22 ms 57908 KB Output is correct
10 Correct 24 ms 59728 KB Output is correct
11 Correct 24 ms 61788 KB Output is correct
12 Correct 24 ms 62020 KB Output is correct
13 Correct 25 ms 61920 KB Output is correct
14 Correct 26 ms 61780 KB Output is correct
15 Correct 25 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 59736 KB Output is correct
2 Correct 34 ms 59992 KB Output is correct
3 Correct 63 ms 65344 KB Output is correct
4 Correct 115 ms 74576 KB Output is correct
5 Correct 33 ms 59928 KB Output is correct
6 Correct 20 ms 56156 KB Output is correct
7 Correct 119 ms 74896 KB Output is correct
8 Correct 78 ms 68692 KB Output is correct
9 Correct 180 ms 84964 KB Output is correct
10 Correct 145 ms 78420 KB Output is correct
11 Correct 167 ms 81544 KB Output is correct
12 Correct 182 ms 81464 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 93400 KB Output is correct
2 Correct 308 ms 93264 KB Output is correct
3 Correct 306 ms 93524 KB Output is correct
4 Correct 303 ms 93264 KB Output is correct
5 Correct 305 ms 93400 KB Output is correct
6 Correct 961 ms 119984 KB Output is correct
7 Correct 886 ms 119892 KB Output is correct
8 Correct 881 ms 120040 KB Output is correct
9 Correct 888 ms 119988 KB Output is correct
10 Correct 962 ms 119840 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 61788 KB Output is correct
2 Correct 19 ms 57688 KB Output is correct
3 Correct 26 ms 61776 KB Output is correct
4 Correct 24 ms 61788 KB Output is correct
5 Correct 25 ms 59740 KB Output is correct
6 Correct 25 ms 59740 KB Output is correct
7 Correct 23 ms 59740 KB Output is correct
8 Correct 25 ms 57692 KB Output is correct
9 Correct 22 ms 57908 KB Output is correct
10 Correct 24 ms 59728 KB Output is correct
11 Correct 24 ms 61788 KB Output is correct
12 Correct 24 ms 62020 KB Output is correct
13 Correct 25 ms 61920 KB Output is correct
14 Correct 26 ms 61780 KB Output is correct
15 Correct 25 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 24 ms 61788 KB Output is correct
2 Correct 19 ms 57688 KB Output is correct
3 Correct 26 ms 61776 KB Output is correct
4 Correct 24 ms 61788 KB Output is correct
5 Correct 25 ms 59740 KB Output is correct
6 Correct 25 ms 59740 KB Output is correct
7 Correct 23 ms 59740 KB Output is correct
8 Correct 25 ms 57692 KB Output is correct
9 Correct 22 ms 57908 KB Output is correct
10 Correct 24 ms 59728 KB Output is correct
11 Correct 24 ms 61788 KB Output is correct
12 Correct 24 ms 62020 KB Output is correct
13 Correct 25 ms 61920 KB Output is correct
14 Correct 26 ms 61780 KB Output is correct
15 Correct 25 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 24 ms 61788 KB Output is correct
2 Correct 19 ms 57688 KB Output is correct
3 Correct 26 ms 61776 KB Output is correct
4 Correct 24 ms 61788 KB Output is correct
5 Correct 25 ms 59740 KB Output is correct
6 Correct 25 ms 59740 KB Output is correct
7 Correct 23 ms 59740 KB Output is correct
8 Correct 25 ms 57692 KB Output is correct
9 Correct 22 ms 57908 KB Output is correct
10 Correct 24 ms 59728 KB Output is correct
11 Correct 24 ms 61788 KB Output is correct
12 Correct 24 ms 62020 KB Output is correct
13 Correct 25 ms 61920 KB Output is correct
14 Correct 26 ms 61780 KB Output is correct
15 Correct 25 ms 61788 KB Output is correct
16 Incorrect 23 ms 61788 KB Output isn't correct
17 Halted 0 ms 0 KB -