oj.uz

Submission #217198

# Submission time Handle Problem Language Result Execution time Memory
217198 2020-03-29T08:22:40 Z VEGAnn Matching (COCI20_matching) C++14
58 / 110
 7 ms 1024 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]--;
                        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.0 / 5.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 6 ms 640 KB Output is correct
14 Correct 7 ms 768 KB Output is correct
15 Correct 6 ms 768 KB Output is correct
16 Correct 6 ms 768 KB Output is correct
17 Correct 7 ms 768 KB Output is correct
18 Correct 6 ms 768 KB Output is correct
19 Correct 6 ms 640 KB Output is correct
20 Correct 6 ms 768 KB Output is correct
21 Correct 6 ms 640 KB Output is correct
22 Correct 6 ms 640 KB Output is correct
23 Correct 7 ms 640 KB Output is correct
24 Correct 7 ms 640 KB Output is correct

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 6 ms 640 KB Output is correct
14 Correct 7 ms 768 KB Output is correct
15 Correct 6 ms 768 KB Output is correct
16 Correct 6 ms 768 KB Output is correct
17 Correct 7 ms 768 KB Output is correct
18 Correct 6 ms 768 KB Output is correct
19 Correct 6 ms 640 KB Output is correct
20 Correct 6 ms 768 KB Output is correct
21 Correct 6 ms 640 KB Output is correct
22 Correct 6 ms 640 KB Output is correct
23 Correct 7 ms 640 KB Output is correct
24 Correct 7 ms 640 KB Output is correct
25 Runtime error 7 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Halted 0 ms 0 KB -