oj.uz

Submission #217190

# Submission time Handle Problem Language Result Execution time Memory
217190 2020-03-29T08:13:44 Z VEGAnn Matching (COCI20_matching) C++14
18 / 110
 7 ms 768 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pii pair<int,int>
#define ft first
#define sd second
#define all(x) x.begin(),x.end()
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long ll;
const int md = int(1e9) + 7;
const int N = 2010;
const int PW = 20;
set<pii> st;
vector<pii> res;
vector<int> vc, vx[N], vy[N];
int n, x[N], y[N], sosed_x[N], sosed_y[N], kol[N];
bool mrk[N];

void BAD(){
    cout << "NE";
    exit(0);
}

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

//    freopen("in.txt","r",stdin);

    cin >> n;
    vc.clear();

    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        vc.PB(x[i]);

        sosed_x[i] = sosed_y[i] = -1;
    }

    sort(all(vc));
    vc.resize(unique(all(vc)) - vc.begin());

    for (int i = 0; i < n; i++)
        x[i] = lower_bound(all(vc), x[i]) - vc.begin();

    vc.clear();
    for (int i = 0; i < n; i++)
        vc.PB(y[i]);

    sort(all(vc));
    vc.resize(unique(all(vc)) - vc.begin());

    for (int i = 0; i < n; i++)
        y[i] = lower_bound(all(vc), y[i]) - vc.begin();

    for (int i = 0; i < n; i++){
        vx[x[i]].PB(i);
        vy[y[i]].PB(i);
    }

    for (int i = 0; i < n; i++){
        if (sz(vx[i]) == 2){
            sosed_x[vx[i][0]] = vx[i][1];
            sosed_x[vx[i][1]] = vx[i][0];
            kol[vx[i][0]]++;
            kol[vx[i][1]]++;
        }

        if (sz(vy[i]) == 2){
            sosed_y[vy[i][0]] = vy[i][1];
            sosed_y[vy[i][1]] = vy[i][0];
            kol[vy[i][0]]++;
            kol[vy[i][1]]++;
        }
    }

    for (int i = 0; i < n; i++)
        st.insert(MP(kol[i], i));

    while (sz(st)){
        int v = (*st.begin()).sd;
        st.erase(st.begin());
        mrk[v] = 1;

        if (kol[v] == 0)
            BAD();

        if (kol[v] == 2){
            for (int i = 0; i < n; i++)
                if (!mrk[i]){
                    mrk[i] = 1;
                    mrk[sosed_x[i]] = 1;

                    res.PB(MP(i, sosed_x[i]));
                }

            break;
        }

        if (sosed_x[v] >= 0){
            int u = sosed_x[v];
            mrk[u] = 1;
            res.PB(MP(u, v));
            st.erase(MP(kol[u], u));
            int bd = max(y[u], y[v]);

            for (int lf = min(y[v], y[u]); lf <= bd; lf++)
                if (sz(vy[lf]) == 2){
                    int n1 = vy[lf][0], n2 = vy[lf][1];

                    if (min(x[n1], x[n2]) < x[v] && max(x[n1], x[n2]) > x[v]){
                        st.erase(MP(kol[n1], n1));
                        st.erase(MP(kol[n2], n2));
                        kol[n1]--;
                        kol[n2]--;
                        st.insert(MP(kol[n1], n1));
                        st.insert(MP(kol[n2], n2));
                        vy[lf].clear();
                        sosed_y[n1] = -1;
                        sosed_y[n2] = -1;
                    }
                }
        } else {
            int u = sosed_y[v];
            mrk[u] = 1;
            res.PB(MP(u, v));
            st.erase(MP(kol[u], u));
            int bd = max(x[u], x[v]);

            for (int lf = min(x[v], x[u]); lf <= bd; lf++)
                if (sz(vx[lf]) == 2){
                    int n1 = vx[lf][0], n2 = vx[lf][1];

                    if (min(y[n1], y[n2]) < y[v] && max(y[n1], y[n2]) > y[v]){
                        st.erase(MP(kol[n1], n1));
                        st.erase(MP(kol[n2], n2));
                        kol[n1]--;
                        kol[n2]--;
                        st.insert(MP(kol[n1], n1));
                        st.insert(MP(kol[n2], n2));
                        vx[lf].clear();
                        sosed_x[n1] = -1;
                        sosed_x[n2] = -1;
                    }
                }
        }
    }

    cout << "DA\n";
    for (pii cr : res)
        cout << cr.ft + 1 << " " << cr.sd + 1 << '\n';

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
0 / 40.0

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

Subtask #5
0 / 52.0

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