oj.uz

Submission #914908

# Submission time Handle Problem Language Result Execution time Memory
914908 2024-01-22T20:51:33 Z davitmarg Towers (NOI22_towers) C++17
18 / 100
 1121 ms 210900 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], x[N];
int used_x[N];
set<int> last_x[N];
int ly[N], ry[N];

void lesgo(int i, int ax)
{
    int pos;
    if (used_x[ax] == 3)
    {
        used_x[ax]--;
        int last_y;
        auto it = last_x[ax].begin();
        ++it;
        last_y = *it;

        if (ly[last_y] == ry[last_y])
        {
            last_x[y[last_y][ly[last_y]].X].erase(last_y);
            ly[last_y]++;
        }
        else if (y[last_y][ly[last_y]].X == ax)
        {
            pos = ly[last_y];
            last_x[y[last_y][pos].X].erase(last_y);
            pos++;
			ly[last_y] = pos;
            if (pos < ry[last_y])
            {
				used_x[y[last_y][pos].X]++;
				lesgo(last_y, y[last_y][pos].X);
                last_x[y[last_y][pos].X].insert(last_y);
			}
        }
        else if(y[last_y][ry[last_y]].X == ax)
        {
            pos = ry[last_y];
            last_x[y[last_y][pos].X].erase(last_y);
            pos--;
            ry[last_y] = pos;
            if (pos > ly[last_y])
            {
                used_x[y[last_y][pos].X]++;
				lesgo(last_y, y[last_y][pos].X);
                last_x[y[last_y][pos].X].insert(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(y[i]));
        sort(all(x[i]), [](pt a, pt b) {return a.Y < b.Y; });
    }

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

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


       ry[i] = y[i].size() - 1;
       if (ly[i] != ry[i])
       {
           used_x[y[i].back().X]++;
           last_x[y[i].back().X].insert(i);
           lesgo(i, y[i].back().X);
       }
    }


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

/*

9
1 1
2 1
3 1
2 2
3 2
4 2
1 3
2 3
3 3


9
2 1
5 1
1 2
2 2
3 2
4 2
2 3
3 4
4 4

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 36 ms 109148 KB Output is correct
2 Correct 31 ms 106988 KB Output is correct
3 Correct 38 ms 109196 KB Output is correct
4 Correct 36 ms 109144 KB Output is correct
5 Correct 37 ms 109196 KB Output is correct
6 Correct 39 ms 107160 KB Output is correct
7 Correct 36 ms 105048 KB Output is correct
8 Correct 39 ms 107144 KB Output is correct
9 Correct 34 ms 105052 KB Output is correct
10 Correct 37 ms 107140 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 109148 KB Output is correct
2 Correct 31 ms 106988 KB Output is correct
3 Correct 38 ms 109196 KB Output is correct
4 Correct 36 ms 109144 KB Output is correct
5 Correct 37 ms 109196 KB Output is correct
6 Correct 39 ms 107160 KB Output is correct
7 Correct 36 ms 105048 KB Output is correct
8 Correct 39 ms 107144 KB Output is correct
9 Correct 34 ms 105052 KB Output is correct
10 Correct 37 ms 107140 KB Output is correct
11 Correct 37 ms 109144 KB Output is correct
12 Correct 36 ms 109188 KB Output is correct
13 Correct 38 ms 109144 KB Output is correct
14 Correct 38 ms 109012 KB Output is correct
15 Correct 39 ms 109140 KB Output is correct
16 Incorrect 36 ms 109148 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 49 ms 106744 KB Output is correct
2 Correct 52 ms 109140 KB Output is correct
3 Correct 84 ms 116932 KB Output is correct
4 Correct 151 ms 131624 KB Output is correct
5 Correct 50 ms 109404 KB Output is correct
6 Correct 33 ms 104280 KB Output is correct
7 Correct 165 ms 131248 KB Output is correct
8 Correct 108 ms 122452 KB Output is correct
9 Correct 239 ms 140024 KB Output is correct
10 Correct 195 ms 134992 KB Output is correct
11 Correct 224 ms 140540 KB Output is correct
12 Correct 224 ms 140624 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 162428 KB Output is correct
2 Correct 470 ms 160596 KB Output is correct
3 Correct 445 ms 160328 KB Output is correct
4 Correct 442 ms 160340 KB Output is correct
5 Correct 473 ms 160336 KB Output is correct
6 Correct 1121 ms 210672 KB Output is correct
7 Correct 1098 ms 210724 KB Output is correct
8 Correct 1119 ms 210852 KB Output is correct
9 Correct 1115 ms 210776 KB Output is correct
10 Correct 1107 ms 210900 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 109148 KB Output is correct
2 Correct 31 ms 106988 KB Output is correct
3 Correct 38 ms 109196 KB Output is correct
4 Correct 36 ms 109144 KB Output is correct
5 Correct 37 ms 109196 KB Output is correct
6 Correct 39 ms 107160 KB Output is correct
7 Correct 36 ms 105048 KB Output is correct
8 Correct 39 ms 107144 KB Output is correct
9 Correct 34 ms 105052 KB Output is correct
10 Correct 37 ms 107140 KB Output is correct
11 Correct 37 ms 109144 KB Output is correct
12 Correct 36 ms 109188 KB Output is correct
13 Correct 38 ms 109144 KB Output is correct
14 Correct 38 ms 109012 KB Output is correct
15 Correct 39 ms 109140 KB Output is correct
16 Incorrect 36 ms 109148 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 109148 KB Output is correct
2 Correct 31 ms 106988 KB Output is correct
3 Correct 38 ms 109196 KB Output is correct
4 Correct 36 ms 109144 KB Output is correct
5 Correct 37 ms 109196 KB Output is correct
6 Correct 39 ms 107160 KB Output is correct
7 Correct 36 ms 105048 KB Output is correct
8 Correct 39 ms 107144 KB Output is correct
9 Correct 34 ms 105052 KB Output is correct
10 Correct 37 ms 107140 KB Output is correct
11 Correct 37 ms 109144 KB Output is correct
12 Correct 36 ms 109188 KB Output is correct
13 Correct 38 ms 109144 KB Output is correct
14 Correct 38 ms 109012 KB Output is correct
15 Correct 39 ms 109140 KB Output is correct
16 Incorrect 36 ms 109148 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 109148 KB Output is correct
2 Correct 31 ms 106988 KB Output is correct
3 Correct 38 ms 109196 KB Output is correct
4 Correct 36 ms 109144 KB Output is correct
5 Correct 37 ms 109196 KB Output is correct
6 Correct 39 ms 107160 KB Output is correct
7 Correct 36 ms 105048 KB Output is correct
8 Correct 39 ms 107144 KB Output is correct
9 Correct 34 ms 105052 KB Output is correct
10 Correct 37 ms 107140 KB Output is correct
11 Correct 37 ms 109144 KB Output is correct
12 Correct 36 ms 109188 KB Output is correct
13 Correct 38 ms 109144 KB Output is correct
14 Correct 38 ms 109012 KB Output is correct
15 Correct 39 ms 109140 KB Output is correct
16 Incorrect 36 ms 109148 KB Output isn't correct
17 Halted 0 ms 0 KB -