oj.uz

Submission #218819

# Submission time Handle Problem Language Result Execution time Memory
218819 2020-04-02T19:23:38 Z Vimmer Matching (COCI20_matching) C++14
58 / 110
 2091 ms 524292 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;

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

unordered_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)
{
    if (psh_dely.find(v) == psh_dely.end()) return;

    vector <pair <int, int> > gr = psh_dely[v];

    while (sz(gr) > 0)
    {
        pair <int, int>  pt = gr.back();

        gr.pop_back();

        ty_del[v].insert(pt);

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

    psh_dely[v] = gr;
}

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 1408 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 1408 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 1408 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 1152 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 1408 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 1152 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 9 ms 1792 KB Output is correct
14 Correct 10 ms 2048 KB Output is correct
15 Correct 11 ms 2048 KB Output is correct
16 Correct 9 ms 1920 KB Output is correct
17 Correct 11 ms 2304 KB Output is correct
18 Correct 9 ms 1792 KB Output is correct
19 Correct 9 ms 1792 KB Output is correct
20 Correct 9 ms 1664 KB Output is correct
21 Correct 7 ms 1664 KB Output is correct
22 Correct 6 ms 1536 KB Output is correct
23 Correct 9 ms 1536 KB Output is correct
24 Correct 42 ms 11000 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 1408 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 1152 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 9 ms 1792 KB Output is correct
14 Correct 10 ms 2048 KB Output is correct
15 Correct 11 ms 2048 KB Output is correct
16 Correct 9 ms 1920 KB Output is correct
17 Correct 11 ms 2304 KB Output is correct
18 Correct 9 ms 1792 KB Output is correct
19 Correct 9 ms 1792 KB Output is correct
20 Correct 9 ms 1664 KB Output is correct
21 Correct 7 ms 1664 KB Output is correct
22 Correct 6 ms 1536 KB Output is correct
23 Correct 9 ms 1536 KB Output is correct
24 Correct 42 ms 11000 KB Output is correct
25 Correct 500 ms 61612 KB Output is correct
26 Correct 679 ms 93624 KB Output is correct
27 Correct 398 ms 46392 KB Output is correct
28 Correct 492 ms 61756 KB Output is correct
29 Correct 285 ms 42888 KB Output is correct
30 Correct 382 ms 59960 KB Output is correct
31 Correct 290 ms 43528 KB Output is correct
32 Correct 429 ms 67644 KB Output is correct
33 Correct 91 ms 11656 KB Output is correct
34 Correct 90 ms 11784 KB Output is correct
35 Correct 68 ms 10244 KB Output is correct
36 Correct 264 ms 18440 KB Output is correct
37 Correct 176 ms 11300 KB Output is correct
38 Runtime error 2091 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)