oj.uz

Submission #699699

# Submission time Handle Problem Language Result Execution time Memory
699699 2023-02-17T19:46:23 Z Lobo Parking (CEOI22_parking) C++17
20 / 100
 112 ms 38740 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]);
                    }
                    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 10 ms 19144 KB Output is correct
2 Correct 13 ms 19028 KB Output is correct
3 Correct 10 ms 19072 KB Output is correct
4 Correct 10 ms 19132 KB Output is correct
5 Correct 10 ms 19028 KB Output is correct
6 Correct 10 ms 19140 KB Output is correct
7 Correct 11 ms 19028 KB Output is correct
8 Correct 10 ms 19028 KB Output is correct
9 Correct 10 ms 19028 KB Output is correct
10 Correct 10 ms 19148 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 32064 KB Output is correct
2 Correct 112 ms 33592 KB Output is correct
3 Correct 70 ms 29128 KB Output is correct
4 Correct 64 ms 29496 KB Output is correct
5 Correct 110 ms 33060 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 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 11 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 13 ms 19212 KB Output is correct
2 Correct 11 ms 19240 KB Output is correct
3 Correct 11 ms 19268 KB Output is correct
4 Runtime error 26 ms 38740 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 10 ms 19144 KB Output is correct
2 Correct 13 ms 19028 KB Output is correct
3 Correct 10 ms 19072 KB Output is correct
4 Correct 10 ms 19132 KB Output is correct
5 Correct 10 ms 19028 KB Output is correct
6 Correct 10 ms 19140 KB Output is correct
7 Correct 11 ms 19028 KB Output is correct
8 Correct 10 ms 19028 KB Output is correct
9 Correct 10 ms 19028 KB Output is correct
10 Correct 10 ms 19148 KB Output is correct
11 Correct 82 ms 32064 KB Output is correct
12 Correct 112 ms 33592 KB Output is correct
13 Correct 70 ms 29128 KB Output is correct
14 Correct 64 ms 29496 KB Output is correct
15 Correct 110 ms 33060 KB Output is correct
16 Incorrect 11 ms 19156 KB Output isn't correct
17 Halted 0 ms 0 KB -