oj.uz

Submission #914888

# Submission time Handle Problem Language Result Execution time Memory
914888 2024-01-22T20:17:01 Z davitmarg Towers (NOI22_towers) C++17
0 / 100
 294 ms 171856 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(pt a)
{
    int pos;
    if (used_x[a.X] == 3)
    {
        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(y[last_y][pos]);
                last_x[y[last_y][pos].X].push_back(last_y);
			}
        }
        else if(y[last_y][ry[last_y]].X == a.X)
        {
            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]);
                last_x[y[last_y][pos].X].push_back(last_y);
            }
        }
    }
    else
        assert(0);
}

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]);
       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());
           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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 63 ms 112704 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 63 ms 112704 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 79 ms 116540 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 294 ms 171856 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 63 ms 112704 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 63 ms 112704 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 63 ms 112704 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -