oj.uz

Submission #699736

# Submission time Handle Problem Language Result Execution time Memory
699736 2023-02-17T21:37:06 Z Lobo Parking (CEOI22_parking) C++17
4 / 100
 92 ms 38732 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/1000;

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

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]);
            out[t[i]]++;
            in[b[i]]++;
        }
    }

    for(int i = 1; i <= n; i++) {
        if(done[i] == 0 && in[i] == 0) {
            ot[out[i]].pb(i);
        }
    }

    vector<pair<int,int>> ans;
    while(true) {
        if(ot[0].size()) {
            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(ot[1].size()) {
            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[out[x]].pb(x);
                }
            }
            t[p1] = i;
            pos[i][1] = p1+m;
        }
        else if(ot[2].size() && 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[out[x]].pb(x);
                }
                else if(in[x] == 1) {
                    sort(all(pos[x]));
                    int j = t[pos[x][0]]+t[pos[x][1]];
                    // cout << x << " " << t[pos[x][0]] << " " << t[pos[x][1]] << endl;
                    ot[out[j]].pb(j);
                }
            }
            b[e] = i;
            t[e] = i;
            pos[i][0] = e;
            pos[i][1] = e+m;
        }
        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[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;
            for(auto x : ans) {
                if(x.fr > m) x.fr-= m;
                if(x.sc > m) x.sc-= m;
                cout << x.fr << " " << x.sc << 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
2.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 10 ms 19028 KB Output is partially correct
2 Partially correct 12 ms 19028 KB Output is partially correct
3 Partially correct 9 ms 19028 KB Output is partially correct
4 Partially correct 10 ms 19088 KB Output is partially correct
5 Partially correct 10 ms 19080 KB Output is partially correct
6 Correct 10 ms 19100 KB Output is correct
7 Partially correct 10 ms 19028 KB Output is partially correct
8 Correct 9 ms 19088 KB Output is correct
9 Correct 10 ms 19028 KB Output is correct
10 Partially correct 10 ms 19028 KB Output is partially correct

Subtask #2
2.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 84 ms 31716 KB Output is partially correct
2 Partially correct 92 ms 32600 KB Output is partially correct
3 Partially correct 56 ms 29140 KB Output is partially correct
4 Partially correct 54 ms 28872 KB Output is partially correct
5 Partially correct 87 ms 32280 KB Output is partially correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 38732 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 38732 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 11 ms 19284 KB Output is partially correct
2 Incorrect 11 ms 19176 KB Extra information in the output file
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 10 ms 19028 KB Output is partially correct
2 Partially correct 12 ms 19028 KB Output is partially correct
3 Partially correct 9 ms 19028 KB Output is partially correct
4 Partially correct 10 ms 19088 KB Output is partially correct
5 Partially correct 10 ms 19080 KB Output is partially correct
6 Correct 10 ms 19100 KB Output is correct
7 Partially correct 10 ms 19028 KB Output is partially correct
8 Correct 9 ms 19088 KB Output is correct
9 Correct 10 ms 19028 KB Output is correct
10 Partially correct 10 ms 19028 KB Output is partially correct
11 Partially correct 84 ms 31716 KB Output is partially correct
12 Partially correct 92 ms 32600 KB Output is partially correct
13 Partially correct 56 ms 29140 KB Output is partially correct
14 Partially correct 54 ms 28872 KB Output is partially correct
15 Partially correct 87 ms 32280 KB Output is partially correct
16 Runtime error 33 ms 38732 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -