oj.uz

Submission #218562

# Submission time Handle Problem Language Result Execution time Memory
218562 2020-04-02T09:39:24 Z Vimmer Matching (COCI20_matching) C++14
11 / 110
 5 ms 384 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100005
#define M ll(998244353)

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef short int si;

//typedef tree<int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> oredered_set;


int x[N], y[N], a[N][2], n;

bool mk[N];

queue <pair <int, int> > qr;

vector <pair <int, int> > vert, gorz;

bool gd(int fr, int sc)
{
    if (x[fr] == x[sc])
    {
        if (y[fr] > y[sc]) swap(fr, sc);

        for (auto it : vert)
        {
            int _fr = it.F, _sc = it.S;

            if (x[_fr] > x[_sc]) swap(_fr, _sc);

            if (y[_fr] < y[fr] || y[sc] < y[_fr]) continue;

            if (x[fr] < x[_fr] || x[_sc] < x[fr]) continue;

            return 0;
        }
    }
    else
    {
        if (x[fr] > x[sc]) swap(fr, sc);

        for (auto it : gorz)
        {
            int _fr = it.F, _sc = it.S;

            if (y[_fr] > y[_sc]) swap(_fr, _sc);

            if (x[_fr] < x[fr] || x[sc] < x[_fr]) continue;

            if (y[fr] < y[_fr] || y[_sc] < y[fr]) continue;

            return 0;
        }
    }

    return 1;
}

void clr(int x)
{
    mk[x] = 1;

    if (a[x][1] != -1) a[x][1] = a[a[x][1]][1] = -1;

    if (a[x][0] != -1) a[x][0] = a[a[x][0]][0] = -1;
}

void fnd()
{
    for (int i = 0; i < n; i++)
    {
        if (mk[i]) continue;

        if (a[i][1] == -1 && a[i][0] == -1) continue;

        if (a[i][1] != -1 && a[i][0] != -1) continue;

        if (a[i][1] != -1) {qr.push({a[i][1], a[a[i][1]][1]}); clr(a[i][1]); clr(i); return;}

        if (a[i][0] != -1) {qr.push({a[i][0], a[a[i][0]][0]}); clr(a[i][0]); clr(i); return;}
    }

    for (int i = 0; i < n; i++)
    {
        if (mk[i]) continue;

        if (a[i][1] == -1 && a[i][0] == -1) continue;

        if (gd(i, a[i][0]) && gd(i, a[i][1])) continue;

        if (!gd(i, a[i][0] && !gd(i, a[i][1]))) continue;

        if (gd(i, a[i][0]))
        {
            qr.push({i, a[i][0]});

            clr(a[i][0]);

            clr(i);

            return;
        }
        else
        {
            qr.push({i, a[i][1]});

            clr(a[i][1]);

            clr(i);

            return;
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (mk[i]) continue;

        if (a[i][1] == -1 && a[i][0] == -1) continue;

        if (!gd(i, a[i][0]) && !gd(i, a[i][1])) continue;

        qr.push({i, a[i][1]});

        clr(a[i][1]);

        clr(i);

        return;
    }
}

int main()
{
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;

    for (int i = 0; i < n; i++) {cin >> x[i] >> y[i]; a[i][0] = a[i][1] = -1;}

    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
          if (x[i] == x[j]) {a[i][0] = j; a[j][0] = i;}
            else if (y[i] == y[j]) {a[i][1] = j; a[j][1] = i;}

    fnd();

    while (sz(qr) > 0)
    {
        int fr = qr.front().F;

        int sc = qr.front().S;

        qr.pop();

        if (gd(fr, sc))
        {
            if (x[fr] == x[sc]) gorz.pb({fr, sc}); else vert.pb({fr, sc});
        }

        fnd();
    }

    if (sz(vert) + sz(gorz) != n / 2) {cout << "NE" << endl; exit(0);}

    cout << "DA" << endl;

    for (auto it : gorz) cout << it.F + 1 << " " << it.S + 1 << endl;

    for (auto it : vert) cout << it.F + 1 << " " << it.S + 1 << endl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Incorrect 4 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Incorrect 4 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Incorrect 4 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -