oj.uz

Submission #699704

# Submission time Handle Problem Language Result Execution time Memory
699704 2023-02-17T20:08:34 Z Lobo Parking (CEOI22_parking) C++17
20 / 100
 107 ms 33632 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], 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(); 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(); 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(); 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);
                }
            }
            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]);
                    }
                    else {
                        assert(false);
                    }

                    vector<int> vec;
                    bool ok = false;
                    for(auto x : g[i]) {
                        if(x == b[j] && ok == false) {
                            ok = true;
                            continue;
                        }
                        vec.pb(x);
                    }
                    g[i] = vec;
                    out[i] = g[i].size();
                    break;
                }
            }
        }
        else {
            break;
        }
    }

    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 11 ms 19028 KB Output is correct
2 Correct 10 ms 19104 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 9 ms 19028 KB Output is correct
5 Correct 10 ms 19092 KB Output is correct
6 Correct 9 ms 19028 KB Output is correct
7 Correct 9 ms 19028 KB Output is correct
8 Correct 10 ms 19140 KB Output is correct
9 Correct 12 ms 19076 KB Output is correct
10 Correct 10 ms 19132 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 31968 KB Output is correct
2 Correct 106 ms 33632 KB Output is correct
3 Correct 63 ms 29092 KB Output is correct
4 Correct 69 ms 29556 KB Output is correct
5 Correct 107 ms 33160 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 19156 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 10 ms 19156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19300 KB Output is correct
2 Correct 12 ms 19156 KB Output is correct
3 Correct 11 ms 19284 KB Output is correct
4 Correct 11 ms 19156 KB Output is correct
5 Correct 10 ms 19200 KB Output is correct
6 Correct 10 ms 19156 KB Output is correct
7 Correct 11 ms 19156 KB Output is correct
8 Incorrect 13 ms 19248 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19028 KB Output is correct
2 Correct 10 ms 19104 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 9 ms 19028 KB Output is correct
5 Correct 10 ms 19092 KB Output is correct
6 Correct 9 ms 19028 KB Output is correct
7 Correct 9 ms 19028 KB Output is correct
8 Correct 10 ms 19140 KB Output is correct
9 Correct 12 ms 19076 KB Output is correct
10 Correct 10 ms 19132 KB Output is correct
11 Correct 89 ms 31968 KB Output is correct
12 Correct 106 ms 33632 KB Output is correct
13 Correct 63 ms 29092 KB Output is correct
14 Correct 69 ms 29556 KB Output is correct
15 Correct 107 ms 33160 KB Output is correct
16 Incorrect 10 ms 19156 KB Output isn't correct
17 Halted 0 ms 0 KB -