Submission #217198

#	Time	Username	Problem	Language	Result	Execution time	Memory
217198		VEGAnn	Matching (COCI20_matching)	C++14	58 / 110	7 ms	1024 KiB

matching

#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]--;
                        if (!mrk[n1]) st.insert(MP(kol[n1], n1));
                        if (!mrk[n2]) 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]--;
                        if (!mrk[n1]) st.insert(MP(kol[n1], n1));
                        if (!mrk[n2]) 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 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 40 / 40
• Subtask 5: 0 / 52