oj.uz

Submission #218817

# Submission time Handle Problem Language Result Execution time Memory
218817 2020-04-02T19:19:43 Z Vimmer Matching (COCI20_matching) C++14
58 / 110
 2500 ms 432304 KB 
#include <bits/stdc++.h>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 100001

using namespace std;

int x[N], y[N], a[N][2], b[N], n, xr[N], yr[N];

set <int> alone;

map <int, set <pair <int, int> > >ty_del;

map <int, vector <pair <int, int> > >psh_dely;

bool mk[N], mkr[N][2];

vector <pair <int, int> > g;

void Push_dely(int v, int tl, int tr)
{
    while (sz(psh_dely[v]) > 0)
    {
        pair <int, int>  pt = psh_dely[v].back();

        psh_dely[v].pop_back();

        ty_del[v].insert(pt);

        if (tl != tr) {psh_dely[v + v].pb(pt); psh_dely[v + v + 1].pb(pt); }
    }
}

void upd_del(int v, int tl, int tr, int l, int r, pair <int, int> val)
{
    if (tl > tr || l > r || r < tl || tr < l) return;

    if (l <= tl && tr <= r) {psh_dely[v].pb(val); return;}

    int md = (tl + tr) >> 1;

    upd_del(v + v, tl, md, l, r, val);

    upd_del(v + v + 1, md + 1, tr, l, r, val);
}

void add_remove(int fr, int sc)
{
    if (!mk[fr])  {if (a[fr][1] != -1) alone.insert(fr); else {cout << "NE" << endl; exit(0);}}

    if (!mk[sc])  {if (a[sc][1] != -1) alone.insert(sc); else {cout << "NE" << endl; exit(0);}}
}

void good_del(int v, int tl, int tr, int pos, int l, int r)
{
    Push_dely(v, tl, tr);

    if (tl == tr)
    {
        set <pair <int, int> > :: iterator it;

        it = ty_del[v].lower_bound({l, -1e9});

        while (it != ty_del[v].end() && (*it).F <= r) {add_remove(b[(*it).S], (*it).S); it++;}
    }
    else
    {
        int md = (tl + tr) >> 1;

        if (pos <= md) good_del(v + v, tl, md, pos, l, r);
          else  good_del(v + v + 1, md + 1, tr, pos, l, r);
    }
}

void seacrh(int fr, int sc)
{
    if (x[fr] > x[sc]) swap(fr, sc);

    good_del(1, 1, N, y[fr], x[fr], x[sc]);
}

void add(int fr, int sc)
{
    g.pb({fr, sc});

    seacrh(fr, sc);
}

void adder(int v)
{
    if (mk[v]) return;

    if (a[v][1] != -1) {add(v, a[v][1]); mk[v] = 1; mk[a[v][1]] = 1; return;}

    cout << "NE" << endl;

    exit(0);
}

void fnd()
{
    while (sz(alone) > 0)
    {
        int v = *alone.begin();

        alone.erase(alone.begin());

        adder(v);
    }

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

        g.pb({i, a[i][0]});

        mk[a[i][0]] = 1;
    }
}

void add_del(int fr, int sc)
{
    if (mkr[fr][0]) return;

    mkr[fr][0] = 1;

    mkr[sc][0] = 1;

    if (y[fr] > y[sc]) swap(fr, sc);

    upd_del(1, 1, N, y[fr], y[sc], {x[fr], fr });
}
int main()
{
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;

    for (int i = 1; i < N; i++) xr[i] = yr[i] = -1;

    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++)
        {
            int X = x[i], Y = y[i];

            if (xr[X] == -1) xr[X] = i; else {a[i][0] = xr[X]; a[xr[X]][0] = i;}

            if (yr[Y] == -1) yr[Y] = i; else {a[i][1] = yr[Y]; a[yr[Y]][1] = i;}
        }

    for (int i = 0; i < n; i++)
    {
        b[i] = a[i][0];

        if (a[i][0] == a[i][1] && a[i][1] == -1) {cout << "NE" << endl; exit(0);}

        if (a[i][0] != -1) add_del(i, a[i][0]);
    }

    for (int i = 0; i < n; i++) if (a[i][0] == -1) adder(i);

    fnd();

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

    cout << "DA" << endl;

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

Subtask #1
5.0 / 5.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1152 KB Output is correct
2 Correct 5 ms 1152 KB Output is correct
3 Correct 5 ms 1152 KB Output is correct
4 Correct 5 ms 1152 KB Output is correct
5 Correct 5 ms 1152 KB Output is correct
6 Correct 5 ms 1152 KB Output is correct
7 Correct 5 ms 1152 KB Output is correct
8 Correct 5 ms 1152 KB Output is correct
9 Correct 5 ms 1280 KB Output is correct
10 Correct 5 ms 1152 KB Output is correct
11 Correct 5 ms 1152 KB Output is correct
12 Correct 5 ms 1152 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1152 KB Output is correct
2 Correct 5 ms 1152 KB Output is correct
3 Correct 5 ms 1152 KB Output is correct
4 Correct 5 ms 1152 KB Output is correct
5 Correct 5 ms 1152 KB Output is correct
6 Correct 5 ms 1152 KB Output is correct
7 Correct 5 ms 1152 KB Output is correct
8 Correct 5 ms 1152 KB Output is correct
9 Correct 5 ms 1280 KB Output is correct
10 Correct 5 ms 1152 KB Output is correct
11 Correct 5 ms 1152 KB Output is correct
12 Correct 5 ms 1152 KB Output is correct
13 Correct 10 ms 1792 KB Output is correct
14 Correct 17 ms 2108 KB Output is correct
15 Correct 13 ms 2176 KB Output is correct
16 Correct 11 ms 2048 KB Output is correct
17 Correct 15 ms 2432 KB Output is correct
18 Correct 11 ms 1920 KB Output is correct
19 Correct 10 ms 1792 KB Output is correct
20 Correct 10 ms 1792 KB Output is correct
21 Correct 7 ms 1664 KB Output is correct
22 Correct 7 ms 1664 KB Output is correct
23 Correct 10 ms 1664 KB Output is correct
24 Correct 69 ms 11256 KB Output is correct

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1152 KB Output is correct
2 Correct 5 ms 1152 KB Output is correct
3 Correct 5 ms 1152 KB Output is correct
4 Correct 5 ms 1152 KB Output is correct
5 Correct 5 ms 1152 KB Output is correct
6 Correct 5 ms 1152 KB Output is correct
7 Correct 5 ms 1152 KB Output is correct
8 Correct 5 ms 1152 KB Output is correct
9 Correct 5 ms 1280 KB Output is correct
10 Correct 5 ms 1152 KB Output is correct
11 Correct 5 ms 1152 KB Output is correct
12 Correct 5 ms 1152 KB Output is correct
13 Correct 10 ms 1792 KB Output is correct
14 Correct 17 ms 2108 KB Output is correct
15 Correct 13 ms 2176 KB Output is correct
16 Correct 11 ms 2048 KB Output is correct
17 Correct 15 ms 2432 KB Output is correct
18 Correct 11 ms 1920 KB Output is correct
19 Correct 10 ms 1792 KB Output is correct
20 Correct 10 ms 1792 KB Output is correct
21 Correct 7 ms 1664 KB Output is correct
22 Correct 7 ms 1664 KB Output is correct
23 Correct 10 ms 1664 KB Output is correct
24 Correct 69 ms 11256 KB Output is correct
25 Correct 687 ms 63196 KB Output is correct
26 Correct 965 ms 95728 KB Output is correct
27 Correct 531 ms 47468 KB Output is correct
28 Correct 668 ms 63344 KB Output is correct
29 Correct 414 ms 45432 KB Output is correct
30 Correct 560 ms 62072 KB Output is correct
31 Correct 419 ms 46072 KB Output is correct
32 Correct 619 ms 69876 KB Output is correct
33 Correct 140 ms 13432 KB Output is correct
34 Correct 146 ms 13620 KB Output is correct
35 Correct 107 ms 11768 KB Output is correct
36 Correct 364 ms 20336 KB Output is correct
37 Correct 234 ms 12400 KB Output is correct
38 Execution timed out 2609 ms 432304 KB Time limit exceeded