oj.uz

Submission #218841

# Submission time Handle Problem Language Result Execution time Memory
218841 2020-04-02T20:08:48 Z Vimmer Matching (COCI20_matching) C++14
58 / 110
 1955 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 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 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 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 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 2104 KB Output is correct
15 Correct 10 ms 2048 KB Output is correct
16 Correct 10 ms 1920 KB Output is correct
17 Correct 11 ms 2432 KB Output is correct
18 Correct 9 ms 1792 KB Output is correct
19 Correct 9 ms 1664 KB Output is correct
20 Correct 9 ms 1792 KB Output is correct
21 Correct 7 ms 1664 KB Output is correct
22 Correct 8 ms 1664 KB Output is correct
23 Correct 9 ms 1536 KB Output is correct
24 Correct 40 ms 11008 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 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 2104 KB Output is correct
15 Correct 10 ms 2048 KB Output is correct
16 Correct 10 ms 1920 KB Output is correct
17 Correct 11 ms 2432 KB Output is correct
18 Correct 9 ms 1792 KB Output is correct
19 Correct 9 ms 1664 KB Output is correct
20 Correct 9 ms 1792 KB Output is correct
21 Correct 7 ms 1664 KB Output is correct
22 Correct 8 ms 1664 KB Output is correct
23 Correct 9 ms 1536 KB Output is correct
24 Correct 40 ms 11008 KB Output is correct
25 Correct 491 ms 62268 KB Output is correct
26 Correct 661 ms 94396 KB Output is correct
27 Correct 395 ms 47544 KB Output is correct
28 Correct 481 ms 63036 KB Output is correct
29 Correct 269 ms 43912 KB Output is correct
30 Correct 395 ms 61240 KB Output is correct
31 Correct 274 ms 44168 KB Output is correct
32 Correct 439 ms 69052 KB Output is correct
33 Correct 85 ms 12684 KB Output is correct
34 Correct 87 ms 12804 KB Output is correct
35 Correct 75 ms 11272 KB Output is correct
36 Correct 239 ms 19460 KB Output is correct
37 Correct 169 ms 12324 KB Output is correct
38 Runtime error 1955 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)