oj.uz

Submission #488467

# Submission time Handle Problem Language Result Execution time Memory
488467 2021-11-19T07:46:38 Z madv809 Matching (COCI20_matching) C++14
11 / 110
 17 ms 28496 KB 
#include<bits/stdc++.h>
#define LL long long
#define REP(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOR(i, a, b) for(int i = (a); i <= (b - 1); ++i)
#define pii pair<int, int>
#define pLL pair<LL, LL>
#define X first
#define Y second

#define pb push_back
#define ef else if
using namespace std;
const int mxn = 1e5 + 5;
const int mxk = 2e3 + 5;
const int INF = 1e9 + 7;
const LL base = 64319;
const LL MOD = 2928127154483;
vector<int> ox[mxn], oy[mxn], same_ox[mxn], same_oy[mxn];
int x[mxn], y[mxn];
vector<pii> res;
set<int> seg[4*mxn];
bool vis[mxn];

void update(int L, int R, int h, int l, int r, int pos)
{
    if (r < L || R < l) return;
    if (L <= l && r <= R)
    {
        seg[pos].insert(h);
        return;
    }

    int mid = (l + r)>>1;
    update(L, R, h, l, mid, pos << 1);
    update(L, R, h, mid + 1, r, pos << 1 | 1);
}

bool get(int x, int L, int H, int l, int r, int pos)
{
    if (x < l || r < x) return 0;
    auto it = seg[pos].lower_bound(L);
    if (it != seg[pos].end())
        if (L <= *it && *it <= H) return 1;
    if (l == r) return 0;

    int mid = (l + r)>>1;
    return (get(x, L, H, l, mid, pos << 1)||get(x, L, H, mid + 1, r, pos << 1 | 1));
}

int main()
{
    //freopen("D:\\test.txt", "r", stdin);
    //freopen("D:\\test2.txt", "w", stdout);
    int n; cin >> n;
    REP(i, 1, n)
    {
        scanf("%d%d", &x[i], &y[i]);
        if (ox[x[i]].size() == 0) ox[x[i]].pb(i);
        else
        {
            same_ox[i].pb(ox[x[i]].back());
            same_ox[ox[x[i]].back()].pb(i);
            ox[x[i]].pop_back();
        }

        if (oy[y[i]].size() == 0) oy[y[i]].pb(i);
        else
        {
            same_oy[i].pb(oy[y[i]].back());
            same_oy[oy[y[i]].back()].pb(i);
            oy[y[i]].pop_back();
        }
    }

    REP(i, 1, n) if (same_ox[i].size() == 0 && same_oy[i].size() == 0)
    {
        printf("NE");
        return 0;
    }

    bool ok = 1;
    REP(i, 1, n) if (same_ox[i].size() == 0) {ok = 0; break;}
    if (ok)
    {
        printf("DA\n");
        REP(u, 1, n) if (!vis[u])
        {
            int v = same_ox[u].back();
            printf("%d %d\n", u, v);
            vis[u] = vis[v] = 1;
        }
        return 0;
    }

    vector<int> de;
    REP(i, 1, n) if (same_oy[i].size() == 1 && same_ox[i].size() == 0)
        de.pb(i);

    while(de.size())
    {
        int u = de.back(); de.pop_back();
        if (vis[u]) continue;
        vis[u] = 1;
        int v = same_oy[u].back(); same_oy[u].pop_back();
        res.pb({u, v}); vis[v] = 1;
        same_oy[v].pop_back();
        if (same_ox[v].size() != 0)
        {
            int k = same_ox[v].back();
            same_ox[v].pop_back();
            same_ox[k].pop_back();
            if (same_oy[k].size() == 0)
            {
                printf("NE");
                return 0;
            }
            else de.pb(k);
        }
        update(min(x[u], x[v]), max(x[u], x[v]), y[u], 1, mxn, 1);
    }

    REP(u, 1, n) if (!vis[u])
    {
        if (same_ox[u].size() == 0)
        {
            printf("NE");
            return 0;
        }
        int v = same_ox[u].back(); same_ox[u].pop_back();
        if (!get(x[u], min(y[v], y[u]), max(y[v], y[u]), 1, mxn, 1))
        {
            res.pb({u, v});
            vis[u] = vis[v] = 1;
        }
        else
        {
            printf("NE");
            return 0;
        }
    }

    printf("DA\n");
    for (pii t : res)
        printf("%d %d\n", t.X, t.Y);
}

Compilation message

matching.cpp: In function 'int main()':
matching.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d%d", &x[i], &y[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28496 KB Output is correct
2 Correct 15 ms 28492 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28496 KB Output is correct
2 Correct 15 ms 28492 KB Output is correct
3 Correct 14 ms 28492 KB Output is correct
4 Correct 15 ms 28484 KB Output is correct
5 Correct 14 ms 28476 KB Output is correct
6 Correct 14 ms 28496 KB Output is correct
7 Correct 17 ms 28496 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28496 KB Output is correct
2 Correct 15 ms 28492 KB Output is correct
3 Correct 14 ms 28492 KB Output is correct
4 Correct 15 ms 28484 KB Output is correct
5 Correct 14 ms 28476 KB Output is correct
6 Correct 14 ms 28496 KB Output is correct
7 Correct 17 ms 28496 KB Output is correct
8 Correct 15 ms 28464 KB Output is correct
9 Incorrect 15 ms 28424 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28496 KB Output is correct
2 Correct 15 ms 28492 KB Output is correct
3 Correct 14 ms 28492 KB Output is correct
4 Correct 15 ms 28484 KB Output is correct
5 Correct 14 ms 28476 KB Output is correct
6 Correct 14 ms 28496 KB Output is correct
7 Correct 17 ms 28496 KB Output is correct
8 Correct 15 ms 28464 KB Output is correct
9 Incorrect 15 ms 28424 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28496 KB Output is correct
2 Correct 15 ms 28492 KB Output is correct
3 Correct 14 ms 28492 KB Output is correct
4 Correct 15 ms 28484 KB Output is correct
5 Correct 14 ms 28476 KB Output is correct
6 Correct 14 ms 28496 KB Output is correct
7 Correct 17 ms 28496 KB Output is correct
8 Correct 15 ms 28464 KB Output is correct
9 Incorrect 15 ms 28424 KB Output isn't correct
10 Halted 0 ms 0 KB -