oj.uz

Submission #699756

# Submission time Handle Problem Language Result Execution time Memory
699756 2023-02-17T22:35:19 Z Lobo Parking (CEOI22_parking) C++17
12 / 100
 161 ms 57816 KB 
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 4e5+10;

int n, m, b[maxn], t[maxn], in[maxn], done[maxn], out[maxn];
vector<int> pos[maxn], g[maxn], gt[maxn];

int mnin(int u) {
    int ans = 3;
    for(auto v : g[u]) {
        ans = min(ans, in[v]);
    }
    return ans;
}

void solve() {
    cin >> n >> m;
    vector<int> ept;
    int cntdone = 0;
    for(int i = 1; i <= m; i++) {
        cin >> b[i] >> t[i];
        
        if(b[i] == 0) {
            ept.pb(i);
            continue;
        }

        if(b[i] != 0) pos[b[i]].pb(i);
        if(t[i] != 0) pos[t[i]].pb(i+m);

        if(b[i] == t[i]) {
            done[b[i]] = 1; cntdone++;
        }
        else if(b[i] != 0 && t[i] != 0) {
            g[t[i]].pb(b[i]);
            gt[b[i]].pb(t[i]);
            out[t[i]]++;
            in[b[i]]++;
        }
    }

    set<pair<pair<int,int>,int>> ot; // out, minin, i
    for(int i = 1; i <= n; i++) {
        if(done[i] == 0 && in[i] == 0) {
            // ot[out[i]].pb(i);
            ot.insert(mp(mp(out[i],mnin(i)),i));
        }
    }

    vector<pair<int,int>> ans;
    while(true) {
        if(ot.size()) {
            int i = ot.begin()->sc;
            ot.erase(ot.begin());
            if(done[i]) continue;
            if(out[i] == 0) {
                // int i = ot[0].back(); ot[0].pop_back(); 
                // if(done[i]) continue;
                done[i] = 1; 
                cntdone++;
                sort(all(pos[i]));
                int p1 = pos[i][0];
                int p2 = pos[i][1];
                ans.pb(mp(p1,p2));
                b[p1] = 0;
                t[p2] = i;
                ept.pb(p1);
                pos[i][0] = p2+m;
            }
            else if(out[i] == 1) {
                // int i = ot[1].back(); ot[1].pop_back(); 
                // if(done[i]) continue;
                done[i] = 1; 
                cntdone++;
                sort(all(pos[i]));
                int p1 = pos[i][0];
                int p2 = pos[i][1];
                ans.pb(mp(p2,p1));
                t[p2-m] = 0;
                for(auto x : g[i]) {
                    if(--in[x] == 0) {
                        ot.insert(mp(mp(out[x],mnin(x)),x));
                    }
                    else {
                        for(auto y : gt[x]) {
                            if(!done[y]) {
                                ot.insert(mp(mp(out[y],mnin(y)),y));
                            }
                        }
                    }
                }
                t[p1] = i;
                pos[i][1] = p1+m;
            }
            else if(out[i] == 2 && ept.size()) {
                // int i = ot[2].back(); ot[2].pop_back(); 
                // if(done[i]) continue;
                done[i] = 1; 
                cntdone++;
                int e = ept.back(); ept.pop_back();
                sort(all(pos[i]));
                int p1 = pos[i][0];
                int p2 = pos[i][1];
                ans.pb(mp(p1,e));
                ans.pb(mp(p2,e));
                t[p1-m] = 0;
                t[p2-m] = 0;
                for(auto x : g[i]) {
                    if(--in[x] == 0) {
                        ot.insert(mp(mp(out[x],mnin(x)),x));
                    }
                    else {
                        for(auto y : gt[x]) {
                            if(!done[y]) {
                                ot.insert(mp(mp(out[y],mnin(y)),y));
                            }
                        }
                    }
                }
                b[e] = i;
                t[e] = i;
                pos[i][0] = e;
                pos[i][1] = e+m;
            }
            else {
                break;
            }
        }
        else if(ept.size() && cntdone != n) {
            for(int j = 1; j <= m; j++) {
                if(b[j] != t[j]) {
                    int i = t[j];
                    int e = ept.back(); ept.pop_back();
                    sort(all(pos[i]));
                    ans.pb(mp(j,e));
                    t[j] = 0;
                    b[e] = i;
                    if(pos[i][0] == j+m) pos[i][0] = e;
                    else pos[i][1] = e;
                    if(--in[b[j]] == 0) {
                        ot.insert(mp(mp(out[b[j]],mnin(b[j])),b[j]));
                        // ot[out[b[j]]].pb(b[j]);
                    }
                    assert((in[b[j]] == 0 && out[b[j]] == 1));
                    assert(g[i].size() == 1);
                    g[i].clear();
                    out[i] = 0;
                    break;
                }
            }
        }
        else {
            break;
        }
    }

    // if(m-n != 0) {
    //     assert(ept.size() != 0);
    // }

    for(int i = 1; i <= n; i++) {
        if(done[i] == 0) {
            cout << -1 << endl;
            return;
        }
    }
    cout << ans.size() << endl;
    for(auto x : ans) {
        if(x.fr > m) x.fr-= m;
        if(x.sc > m) x.sc-= m;
        cout << x.fr << " " << x.sc << endl;
    }


}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28500 KB Output is correct
2 Correct 15 ms 28480 KB Output is correct
3 Correct 14 ms 28500 KB Output is correct
4 Correct 14 ms 28500 KB Output is correct
5 Correct 15 ms 28544 KB Output is correct
6 Correct 15 ms 28500 KB Output is correct
7 Correct 14 ms 28464 KB Output is correct
8 Correct 14 ms 28500 KB Output is correct
9 Correct 15 ms 28496 KB Output is correct
10 Correct 18 ms 28524 KB Output is correct

Subtask #2
2.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 125 ms 44132 KB Output is partially correct
2 Partially correct 161 ms 46776 KB Output is partially correct
3 Partially correct 81 ms 41204 KB Output is partially correct
4 Partially correct 79 ms 41324 KB Output is partially correct
5 Partially correct 160 ms 46496 KB Output is partially correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 28628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 28628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 15 ms 28704 KB Output is partially correct
2 Correct 15 ms 28640 KB Output is correct
3 Partially correct 18 ms 28628 KB Output is partially correct
4 Runtime error 37 ms 57816 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28500 KB Output is correct
2 Correct 15 ms 28480 KB Output is correct
3 Correct 14 ms 28500 KB Output is correct
4 Correct 14 ms 28500 KB Output is correct
5 Correct 15 ms 28544 KB Output is correct
6 Correct 15 ms 28500 KB Output is correct
7 Correct 14 ms 28464 KB Output is correct
8 Correct 14 ms 28500 KB Output is correct
9 Correct 15 ms 28496 KB Output is correct
10 Correct 18 ms 28524 KB Output is correct
11 Partially correct 125 ms 44132 KB Output is partially correct
12 Partially correct 161 ms 46776 KB Output is partially correct
13 Partially correct 81 ms 41204 KB Output is partially correct
14 Partially correct 79 ms 41324 KB Output is partially correct
15 Partially correct 160 ms 46496 KB Output is partially correct
16 Incorrect 14 ms 28628 KB Output isn't correct
17 Halted 0 ms 0 KB -